Как я могу отсортировать числа лексикографически? - PullRequest
Новая
       30

Как я могу отсортировать числа лексикографически?

13 голосов
/ 19 мая 2009

Вот сценарий.

Мне дан массив 'A' целых чисел. Размер массива не фиксирован. Функция, которую я должен написать, может быть вызвана один раз с массивом из нескольких целых чисел, а в другой раз она может даже содержать тысячи целых чисел. Кроме того, каждое целое число не обязательно должно содержать одинаковое количество цифр.

Я должен «отсортировать» числа в массиве так, чтобы в результирующем массиве были целые числа, упорядоченные лексикографическим образом (т.е. они отсортированы на основе их строковых представлений. Здесь «123» - строковое представление 123) , Обратите внимание, что выходные данные должны содержать только целые числа, а не их строковые эквиваленты.

Например: , если ввод:

[12 | 2434 | 23 | 1 | 654 | 222 | 56 | 100000]

Тогда вывод должен быть:

[1 | 100000 | 12 | 222 | 23 | 2434 | 56 | 654]

Мой первоначальный подход: Я преобразовал каждое целое число в его строковый формат, затем добавил нули справа от него, чтобы все целые числа содержали одинаковое количество цифр (это был грязный шаг, так как он включал отслеживание и т. Д. что делает решение очень неэффективным), а затем сделал основную сортировку. Наконец, я удалил дополненные нули, преобразовал строки обратно в их целые числа и поместил их в получившийся массив. Это было очень неэффективное решение.

Меня убеждают, что решение не нуждается в заполнении и т. Д., И есть простое решение, в котором вам просто нужно как-то обработать числа (некоторая обработка битов?), Чтобы получить результат.

Какое космическое наиболее эффективное решение вы можете придумать? Время-накрест?

Если вы даете код, я бы предпочел Java или псевдокод. Но если вас это не устраивает, любой такой язык должен подойти.

Ответы [ 14 ]

0 голосов
/ 19 мая 2009

Один действительно хакерский метод (с использованием C) будет:

  • создать новый массив всех значений, преобразованных в числа с плавающей точкой
  • выполнить сортировку, используя биты мантиссы (значим и) для сравнения

В Java (с здесь ): 

long bits = Double.doubleToLongBits(5894.349580349);

boolean negative = (bits & 0x8000000000000000L) != 0; 
long exponent = bits & 0x7ff0000000000000L >> 52;
long mantissa = bits & 0x000fffffffffffffL;

чтобы вы могли отсортировать по длинному mantissa здесь.

0 голосов
/ 19 мая 2009 
#!/usr/bin/perl

use strict;
use warnings;

my @x = ( 12, 2434, 23, 1, 654, 222, 56, 100000 );

print $_, "\n" for sort @x;

__END__

Некоторые моменты времени ... Во-первых, с пустым @x: 

C:\Temp> timethis s-empty
TimeThis :  Elapsed Time :  00:00:00.188

Теперь с 10 000 случайно сгенерированных элементов: 

TimeThis :  Elapsed Time :  00:00:00.219

Сюда входит время, необходимое для генерации 10000 элементов, но не время вывода их на консоль. Выход добавляет около секунды.

Итак, сэкономьте немного времени программиста; -)

0 голосов
/ 19 мая 2009

Возможная оптимизация: вместо этого:

Я преобразовал каждое целое число в его строковый формат, затем добавил нули справа от него, чтобы все целые числа содержали одинаковое количество цифр

Вы можете умножить каждое число на (10 ^ N - log10 (число)), причем N - это число, большее чем log10 любого из ваших чисел.

0 голосов
/ 19 мая 2009

Если вы планируете экономить пространство, я бы попробовал просто выполнить работу в функции сравнения вида 

int compare(int a, int b) {
   // convert a to string
   // convert b to string
   // return -1 if a < b, 0 if they are equal, 1 if a > b
}

Если он слишком медленный (наверняка, он медленнее, чем предварительная обработка), отследите где-нибудь преобразования, чтобы функция сравнения не выполняла их.

Страница:
...