Сортировка совпадающих массивов в Java

Question

Допустим, у меня есть два массива (на Java),

int [] числа; и int [] colors;

Каждый i-й элемент чисел соответствует его i-му элементу в цветах. Ex, числа = {4,2,1} цвета = {0x11, 0x24, 0x01}; Означает, что число 4 - цвет 0x11, число 2 - 0x24 и т. Д.

Я хочу отсортировать массив чисел, но тогда он у меня будет, чтобы каждый элемент соответствовал своей паре по цветам.

Ex. числа = {1,2,4}; цвета = {0x01,0x24,0x11};

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

Примечание. Я знаю, что «лучшее» решение - создать класс для двух элементов и использовать собственный компаратор. Этот вопрос предназначен для того, чтобы задать людям самый быстрый способ кодирования этого. Представьте себе, что вы участвуете в соревновании по программированию, вам не хотелось бы создавать все эти дополнительные классы, анонимные классы для компаратора и т. Д. Еще лучше, забудьте о Java; как бы вы написали это в C?

Answer 1

Вы можете использовать sort () с пользовательским компаратором, если вы сохранили третий массив с индексом и отсортировали по нему, оставив данные без изменений.

Пример кода Java:

Integer[] idx = new Integer[numbers.length];
for( int i = 0 ; i < idx.length; i++ ) idx[i] = i;              
Arrays.sort(idx, new Comparator<Integer>() {
    public int compare(Integer i1, Integer i2) {                        
        return Double.compare(numbers[i1], numbers[i2]);
    }                   
});

// numbers[idx[i]] is the sorted number at index i
// colors[idx[i]] is the sorted color at index i

Обратите внимание, что вы должны использовать Integer вместо int, или вы не можете использовать собственный компаратор.

Answer 2

Кажется, что самое чистое, что нужно сделать, это создать собственный класс свойств, реализующий Comparable. Например:

class Color implements Comparable {
  private int number;
  private int color;

  // (snip ctor, setters, etc.)

  public int getNumber() {
    return number;
  }
  public int getColor() {
    return color;
  }

  public int compareTo(Color other) {
    if (this.getNumber() == other.getNumber) {
      return 0;
    } else if (this.getNumber() > other.getNumber) {
      return 1;
    } else {
      return -1;
    }
  }
}

Затем вы можете отделить свой алгоритм сортировки от логики упорядочения (вы можете использовать Collections.sort, если вы используете List вместо массива), и, самое главное, вам не придется беспокоиться о том, как получить два массива из синхронизации.

Answer 3

Если вы хотите выделить дополнительное пространство, вы можете сгенерировать другой массив, назовите его extra с такими элементами:

extra = [0,1,...,numbers.length-1]

Затем вы можете отсортировать этот дополнительный массив, используя Arrays.sort () с пользовательским компаратором (который при сравнении элементов i и j действительно сравнивает числа [extra [i]] и числа [extra [j]]). Таким образом, после сортировки дополнительного массива extra [0] будет содержать индекс наименьшего числа и, поскольку числа и цвета не перемещаются, соответствующий цвет.
Это не очень хорошо, но это делает работу, и я не могу придумать более легкий способ сделать это.

Как примечание, на соревнованиях я обычно нахожу шаблонные пары C ++ и хорошие карты незаменимыми;)

Answer 4

Пример, иллюстрирующий использование третьего индексного массива. Не уверен, что это лучшая реализация.

<pre><br> import java.util.*;</p> <pre><code>public class Sort { private static void printTable(String caption, Integer[] numbers, Integer[] colors, Integer[] sortOrder){ System.out.println(caption+ "\nNo Num Color"+ "\n----------------"); for(int i=0;i<sortOrder.length;i++){ System.out.printf("%x %d %d\n", i,numbers[sortOrder[i]],colors[sortOrder[i]]); } } public static void main(String[] args) { final Integer[] numbers = {1,4,3,4,2,6}; final Integer[] colors = {0x50,0x34,0x00,0xfe,0xff,0xff}; Integer[] sortOrder = new Integer[numbers.length]; // Create index array. for(int i=0; i<sortOrder.length; i++){ sortOrder[i] = i; } printTable("\nNot sorted",numbers, colors, sortOrder); Arrays.sort(sortOrder,new Comparator<Integer>() { public int compare(Integer a, Integer b){ return numbers[b]-numbers[a]; }}); printTable("\nSorted by numbers",numbers, colors, sortOrder); Arrays.sort(sortOrder,new Comparator<Integer>() { public int compare(Integer a, Integer b){ return colors[b]-colors[a]; }}); printTable("\nSorted by colors",numbers, colors, sortOrder); } }

Вывод должен выглядеть так:

Not sorted
No   Num   Color
----------------
0    1     80
1    4     52
2    3     0
3    4     254
4    2     255
5    6     255

Sorted by numbers
No   Num   Color
----------------
0    6     255
1    4     52
2    4     254
3    3     0
4    2     255
5    1     80

Sorted by colors
No   Num   Color
----------------
0    6     255
1    2     255
2    4     254
3    1     80
4    4     52
5    3     0

Answer 5

Мне нравится решение @ tovare. Создайте массив указателей:

int ptr[] = { 1, 2, 3 };

и затем при сортировке по числам меняйте значения в ptr, а не в числах. Затем получите доступ через массив ptr, например

for (int i = 0; i < ptr.length; i++)
{
   printf("%d %d\n", numbers[ptr[i]], colors[ptr[i]]);
}

Обновление: хорошо, похоже, другие избили меня до этого. Нет опыта для меня.

Answer 6

Почему бы не представить объект, представляющий число и цвет, и реализовать для этого функцию компаратора?

Кроме того, вам действительно нужен массив, почему бы не использовать что-то, производное от Collection?

Answer 7

Одним из быстрых способов взлома было бы объединение двух массивов со сдвигами битов. Создайте массив значений long, так чтобы старшие 32 бита были числом, а младшие 32 бита - цветом. Используйте метод сортировки, а затем распакуйте.

Answer 8

Полагаю, вы хотите оптимизировать производительность, пытаясь избежать использования массива объектов (что может вызвать болезненное событие GC). К сожалению, нет общего решения, подумал. Но для вашего конкретного случая, в котором числа отличаются друг от друга, могут быть созданы только два массива.

/**
 * work only for array of different numbers
 */
private void sortPairArray(int[] numbers, int[] colors) {
    int[] tmpNumbers = Arrays.copyOf(numbers, numbers.length);
    int[] tmpColors = Arrays.copyOf(colors, colors.length);
    Arrays.sort(numbers);
    for (int i = 0; i < tmpNumbers.length; i++) {
        int number = tmpNumbers[i];
        int index = Arrays.binarySearch(numbers, number); // surely this will be found
        colors[index] = tmpColors[i];
    }
}

Два отсортированных массива можно заменить на Int2IntOpenHashMap , который работает быстрее, но использование памяти может быть в два раза.

Answer 9

Кредит @tovare за оригинальный лучший ответ.

Мой ответ ниже удаляет (сейчас) ненужный автобокс через зависимость Maven {net.mintern: primitive: 1.2.2} из этого ответа: https://stackoverflow.com/a/27095994/257299

int[] idx = new int[numbers.length];
for( int i = 0 ; i < idx.length; i++ ) idx[i] = i;
final boolean isStableSort = false;
Primitive.sort(idx,
               (i1, i2) -> Double.compare(numbers[i1], numbers[i2]),
               isStableSort);

// numbers[idx[i]] is the sorted number at index i
// colors[idx[i]] is the sorted color at index i

Answer 10

Достаточно ли будет написать собственный метод сортировки? Простая пузырьковая сортировка, вероятно, будет быстрой для кодирования (и получится правильно). Нет необходимости в дополнительных классах или компараторах.