Сортировка совпадающих массивов в Java
10994 просмотра
13 ответа
Допустим, у меня есть два массива (на 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 Источник Размещён: 13.11.2019 11:30Ответы (13)
20 плюса
Вы можете использовать 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
или вы не можете использовать пользовательский компаратор.
8 плюса
Кажется, что самое чистое, что можно сделать, это создать собственный класс свойств, реализующий 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:404 плюса
Если вы захотите выделить дополнительное пространство, вы можете сгенерировать другой массив, назовите его extra с такими элементами:
extra = [0,1,...,numbers.length-1]
Затем вы можете отсортировать этот дополнительный массив, используя Arrays.sort () с пользовательским компаратором (который при сравнении элементов i и j действительно сравнивает числа [extra [i]] и числа [extra [j]]). Таким образом, после сортировки дополнительного массива extra [0] будет содержать индекс наименьшего числа и, поскольку числа и цвета не перемещаются, соответствующий цвет.
Это не очень хорошо, но это делает работу, и я не могу придумать более легкий способ сделать это.
Как примечание, на соревнованиях я обычно нахожу шаблонные пары C ++ и хорошие карты незаменимыми;)
Автор: finrod Размещён: 21.09.2008 09:423 плюса
Почему бы не представить объект для представления числа и цвета и реализовать для этого функцию компаратора?
Кроме того, вам действительно нужен массив, почему бы не использовать что-то, полученное из коллекции?
Автор: JeffFoster Размещён: 21.09.2008 09:343 плюса
Мне нравится решение @ 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:583 плюса
Пример, иллюстрирующий использование третьего индексного массива. Не уверен, что это лучшая реализация.
<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
2 плюса
Одним из быстрых способов взлома было бы объединение двух массивов со сдвигами битов. Создайте массив значений long, так чтобы старшие 32 бита были числом, а младшие 32 бита - цветом. Используйте метод сортировки, а затем распакуйте.
Автор: theycallhimtom Размещён: 21.09.2008 10:241 плюс
Достаточно ли будет написать собственный метод сортировки? Простая пузырьковая сортировка, вероятно, будет быстрой для кодирования (и получится правильно). Нет необходимости в дополнительных классах или компараторах.
Автор: Zach Scrivena Размещён: 21.09.2008 10:031 плюс
Благодарю @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 плюс
Я предполагаю, что вы хотите оптимизировать производительность, пытаясь избежать использования массива объектов (что может вызвать болезненное событие 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:410 плюса
Вам нужно отсортировать массив цветов по его относительному элементу в массиве чисел. Укажите компаратор, который сравнивает числа, и используйте его в качестве сравнения для массива цветов.
Автор: 1800 INFORMATION Размещён: 21.09.2008 09:320 плюса
Самый простой способ сделать это в C, это пузырьковая сортировка + двойные указатели. Конечно, самым быстрым будет быстрая сортировка + два указателя. Конечно, второй указатель поддерживает корреляцию между двумя массивами.
Я бы лучше определил значения, которые хранятся в двух массивах, как структуру, и использовал бы структуру в одном массиве. Тогда используйте быструю сортировку на этом. Вы можете написать общую версию sort, вызвав функцию сравнения, которая затем может быть написана для каждой структуры, но тогда вы уже это знаете :)
Автор: shiva Размещён: 22.09.2008 12:400 плюса
Вопросы из категории :
- java В чем разница между int и Integer в Java и C #?
- java Как я могу определить IP моего маршрутизатора / шлюза в Java?
- java Каков наилучший способ проверки XML-файла по сравнению с XSD-файлом?
- java Как округлить результат целочисленного деления?
- java Преобразование списка <Integer> в список <String>
- java Почему я не могу объявить статические методы в интерфейсе?
- sorting Как вы сортируете словарь по значению?
- sorting Объединить Сортировать связанный список
- sorting Natural (human alpha-numeric) sort in Microsoft SQL 2005
- sorting Как отсортировать список строк?
- sorting Как отсортировать список словарей по значению словаря?
- sorting Сортировка по строке, которая может содержать число
- list Функция транспонирования / распаковки (обратная сторона zip)?
- list How would you make a comma-separated string from a list of strings?
- list Удалить дубликаты из списка <T> в C #
- list Console.WriteLine и общий список
- list Как проверить, если список пуст?
- list Являются ли кортежи более эффективными, чем списки в Python?