Сортировка 2-х мерного массива при сортировке подсчетом


Эти задачи я решаю это:

  1. Сортировать список его ключей
  2. Распечатать соответствующие значения в одной строке, разделенные пробелом
  3. Заменить значения первой половине входного сигнала на "-"
  4. Использование Сортировки Подсчетом

Следующий код работает, но раз, когда дали 1 млн. записей:

public class Solution {

static String[] countingSort(String[][] arr) {
    String[] result = new String[arr.length];
    int[] count = new int[100];
    for(int i=0;i<arr.length;i++) {
        count[Integer.parseInt(arr[i][0])]++;
    }
    for(int i=1;i<count.length;i++) {
      count[i] += count[i-1];
    }
    for(int i=arr.length-1;i>=0;i--) {
        result[count[Integer.parseInt(arr[i][0])]-1] = arr[i][1];
        count[Integer.parseInt(arr[i][0])]--;
    }
    return result;
}

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    String[][] arr = new String[n][2];
    for(int a0 = 0; a0 < n; a0++){
        int a = in.nextInt();
        arr[a0][0] = Integer.toString(a);
        if(a0<n/2) {
            String s =in.next();
            arr[a0][1] = "-";
        } else {
            String s = in.next();
            arr[a0][1] = s;
        }
    }
    in.close();
    String[] result = countingSort(arr);
    for(int i=0;i<result.length;i++) {
        System.out.print(result[i]+" ");
    }
}
  1. входной сигнал вводится в 2 мерный массив. значения заменяются "-" для первой половины значений. [массив: arr]
  2. Массив передается в метод [массив: arrметод: countingSort]
  3. Новый массив размером 100 создается как ключи 0 < key < 100 [массив: count]
  4. вхождений каждого ключа добавляется в созданный массив [массив: count]
  5. значения массива накапливаются [массив: count]
  6. значения соответствующего ключа сортировки в результирующем массиве по массиву кол.
  7. результат возвращается.

Особое беспокойство.

  1. Как может код быть улучшены для того, чтобы повысить производительность и избежать тайм-аута с помощью сортировки подсчетом?
  2. Есть ли другие возможности (сортировка алгоритмы), которые имеют более высокую производительность (может решить проблему быстрее)?


278
3
задан 15 февраля 2018 в 09:02 Источник Поделиться
Комментарии
1 ответ

Алгоритм работает нормально, и нет ничего быстрее, чем считая сортировки. Вам просто нужно использовать единую систему.из.печати:

StringBuilder sb = new StringBuilder();
for (int i = 0; i < result.length; i++) {
sb.append(result[i]).append(" ");
}
System.out.print(sb.toString());

Это быстрее, чем многие отдельные звонки;

1
ответ дан 15 февраля 2018 в 03:02 Источник Поделиться