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

java sorting list

10994 просмотра

13 ответа

183 Репутация автора

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

int [] числа; и int [] цвета;

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

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

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

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

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

Автор: user16773 Источник Размещён: 21.09.2008 09:28

Ответы (13)


0 плюса

103805 Репутация автора

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

Автор: 1800 INFORMATION Размещён: 21.09.2008 09:32

3 плюса

372 Репутация автора

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

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

Автор: JeffFoster Размещён: 21.09.2008 09:34

8 плюса

695 Репутация автора

Кажется, что самое чистое, что можно сделать, это создать собственный класс свойств, реализующий 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 вместо массива), и, что наиболее важно, вам не придется беспокоиться о том, как два массива будут синхронизированы.

Автор: Frank Pape Размещён: 21.09.2008 09:40

4 плюса

1348 Репутация автора

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

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

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

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

Автор: finrod Размещён: 21.09.2008 09:42

20 плюса

2409 Репутация автора

Вы можете использовать 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или вы не можете использовать пользовательский компаратор.

Автор: tovare Размещён: 21.09.2008 09:43

3 плюса

147832 Репутация автора

Мне нравится решение @ 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]]);
}

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

Автор: Paul Tomblin Размещён: 21.09.2008 09:58

1 плюс

25548 Репутация автора

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

Автор: Zach Scrivena Размещён: 21.09.2008 10:03

2 плюса

315 Репутация автора

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

Автор: theycallhimtom Размещён: 21.09.2008 10:24

0 плюса

706 Репутация автора

Самый простой способ сделать это в C, это пузырьковая сортировка + двойные указатели. Конечно, самым быстрым будет быстрая сортировка + два указателя. Конечно, второй указатель поддерживает корреляцию между двумя массивами.

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

Автор: shiva Размещён: 22.09.2008 12:40

3 плюса

2409 Репутация автора

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

<br>
    import java.util.*;<p></p>

<pre>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);
    }
}

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

Не отсортировано
Нет Num Цвет
----------------
0 1 80
1 4 52
2 3 0
3 4 254
4 2 255
5 6 255

Отсортировано по номерам
Нет Num Цвет
----------------
0 6 255
1 4 52
2 4 254
3 3 0
4 2 255
5 1 80

Отсортировано по цветам
Нет Num Цвет
----------------
0 6 255
1 2 255
2 4 254
3 1 80
4 4 52
5 3 0
Автор: tovare Размещён: 22.09.2008 11:44

0 плюса

30925 Репутация автора

Используйте TreeMap

Автор: st0le Размещён: 13.09.2010 09:44

1 плюс

11447 Репутация автора

Благодарю @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
Автор: kevinarpe Размещён: 18.04.2016 11:24

1 плюс

11 Репутация автора

Я предполагаю, что вы хотите оптимизировать производительность, пытаясь избежать использования массива объектов (что может вызвать болезненное событие 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 , который выполняет более быстрый запуск, но использование памяти может быть в два раза.

Автор: Tung Ha Размещён: 04.08.2017 09:41
Вопросы из категории :
32x32