Сортировка массива междунара в лексикографическом порядке

Question

я столкнулся с проблемой, что:

WAP для сортировки простых чисел меньших, чем данный N цифр. Если N равно 40, , выход должен быть 11, 13, 17, 19, 2, 23, 29, 3, 31, 37, 39, 5, 7. Примечание: использование памяти с ограничением.

Получение первичного номера было простым. Но я не мог найти эффективный способ лексикографической сортировки массива integer.

public static void getPrimeNumbers(int limit) { 
     for (int i=2; i<=limit; i++) { 
      if(isPrime(i)) { 
       System.out.println(i); 
      } 
     } 
    } 

    public static boolean isPrime(int number) { 
     for(int j=2; j<number; j++) { 
      if(number%j==0) { 
       return false; 
      } 
     } 
      return true; 
    } 

    public static void lexographicSorting() { 
     int[] input = {2,3,5,7,11,13,17,19}; 
     int[] output = {}; 
     for (int i=0; i<input.length; i++) { 
      for(int j=0; j<input.length; j++) { 
       ////Stuck at this part. 
      } 
     } 
    } 

Answer 1

Учитывая ограничения проблемы, более эффективным способом решения этой проблемы является не использование экземпляров String и Integer вообще. Одной из директив проблемы является ограничение использования памяти. В каждом из ответов до сих пор было значительное влияние на память (преобразование в Integer и String).

Вот решение, которое, скорее всего, будет быстрее, и не выделяет никакой кучной памяти вообще (хотя она имеет рекурсию, поэтому может иметь некоторый эффект стека - примерно то же, что и Arrays.sort()). Это решает проблему из первых принципов, не выделяет отдельный массив для результатов и, следовательно, относительно долго сравнивается с другими решениями, но эти другие решения скрывают массу сложности, которой это решение не имеет. .

// this compare works by converting both values to be in the same 'power of 10', 
// for example, comparing 5 and 20, it will convert 5 to 50, then compare 50 and 20 
// numerically. 
public static final int compareLexographicallyToLimit(final int limit, int a, int b) { 
    if (a == b) { 
     return 0; 
    } 
    if (a > limit || b > limit || a < 0 || b < 0) { 
     return a > b ? 1 : -1; 
    } 

    int max = Math.max(a, b); 
    int nextp10 = 1; 
    while (max > 10) { 
     max /= 10; 
     nextp10 *= 10; 
    } 
    while (a < nextp10) { 
     a *= 10; 
    } 
    while (b < nextp10) { 
     b *= 10; 
    } 
    return a > b ? 1 : -1; 
} 

private static void sortByRules(final int[] input, final int limit, final int from, final int to) { 
    if (from >= to) { 
     return; 
    } 
    int pivot = from; 
    int left = from + 1; 
    int right = to; 
    while (left <= right) { 
     while (left <= right && compareLexographicallyToLimit(limit, input[left], input[pivot]) <= 0) { 
      left++; 
     } 
     while (left <= right && compareLexographicallyToLimit(limit, input[pivot], input[right]) <= 0) { 
      right--; 
     } 
     if (left < right) { 
      int tmp = input[left]; 
      input[left] = input[right]; 
      input[right] = tmp; 
      left++; 
      right--; 
     } 
    } 
    int tmp = input[pivot]; 
    input[pivot] = input[right]; 
    input[right] = tmp; 
    sortByRules(input, limit, from, right-1); 
    sortByRules(input, limit, right+1, to); 

} 

public static void main(String[] args) { 
    int[] input = {2,3,5,7,11,13,17,19,31,37,41, 43, 100}; 
    sortByRules(input, 40, 0, input.length - 1); 
    System.out.println(Arrays.toString(input)); 
    sortByRules(input, 15, 0, input.length - 1); 
    System.out.println(Arrays.toString(input)); 
} 

Answer 2

Единственный возможный способ реализовать свои собственные Comparator, где вы будете конвертировать каждый из двух сравниваемых Integer -s в String объекты и делать сравнение на них.

UPD: Вот пример, как реализовать его:

Integer[] input = {2,3,5,7,11,13,17,19}; 

    Arrays.sort(input, new Comparator<Integer>() { 
     @Override 
     public int compare(Integer o1, Integer o2) { 
      return o1.toString().compareTo(o2.toString()); 
     } 
    }); 

Answer 3

Java String#compareTo уже реализует эту функцию, вы можете получить доступ к нему довольно легко путем преобразования объектов Integer к объектам Струнные и вызов compareTo

Arrays.sort(input, new Comparator<Integer>() { 
    @Override 
    int compareTo(Integer x, Integer y) { 
     return x.toString().compareTo(y.toString()); 
    } 
}; 

Я могу точно сказать, насколько эффективным будет память, вам нужно создать 1 объект Integer для каждого примитивного int в вашем массиве, тогда у вас есть t o создать 1 объект String для каждого объекта Integer, который у вас есть. Таким образом, в создании объекта, вероятно, много накладных расходов.

Answer 4

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

Вы можете отсортировать номера на основе самых значащих цифр. См. Это сообщение для вычисления самой значащей цифры числа: Getting a values most significant digit in Objective C (его следует легко переносить на Java).

По существу, вы можете использовать эту функцию как часть вашего компаратора. Вам понадобится способ разорвать связи (например, цифры с теми же самыми значащими цифрами). Если два номера имеют одни и те же самые значащие цифры, вы можете вырвать их и повторно использовать эту функцию снова и снова столько раз, сколько необходимо (пока вы не сможете считать одно число больше другого или пока не закончите цифры, что указывает что они равны).