Научитесь находить первые N элементов в заданном массиве в Java. Обратите внимание, что мы должны очень четко понимать значение первых N элементов. Предлагаемое решение может потребовать незначительных изменений в зависимости от нашей интерпретации и требований.
Например, в этом руководстве верхние N элементов означают верхние N наибольших элементов в массиве.
1. Найдите первые N элементов с помощью очередей
Структура данных Queue поддерживает порядок элементов на основе их приоритета. Хорошо то, что мы можем определить приоритет, задав пользовательский Comparator.
В приведенных примерах мы хотим найти 3 наибольших значения в массиве целых чисел.
1.1.ПриоритетнаяОчередь
PriorityQueue — это неограниченная приоритетная очередь, основанная на приоритетной куче. Элементы приоритетной очереди упорядочены в соответствии с их естественным порядком, а голова этой очереди — наименьший элемент.
Таким образом, если мы добавим целые числа в эту очередь и продолжим опрашивать элементы, чтобы ограничить ее размер тремя, то по завершении цикла в очереди будут 3 самых больших целых значения.
Integer[] items = {0, 10, 30, 2, 7, 5, 90, 76, 100, 45, 55};PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(3);for(Integer i : items) {priorityQueue.add(i);if(priorityQueue.size() > 3)priorityQueue.poll();}System.out.println("Items are : " + priorityQueue); //[76, 100, 90]1.2. MinMaxPriorityQueue
Класс MinMaxPriorityQueue является частью коллекций Guava. Это двухсторонняя приоритетная очередь, которая обеспечивает постоянный доступ как к своему наименьшему элементу, так и к своему наибольшему элементу, как определено указанным компаратором очереди или естественным порядком.
При сравнении решений с MinMaxPriorityQueue и PriorityQueue нам не нужно выполнять дополнительную операцию опроса и проверять размер очереди при каждой итерации.
Включите последнюю версию Guava из репозитория Maven.
<dependency><groupId>com.google.guava</groupId><artifactId>guava</artifactId><version>${guava-version}</version></dependency>Integer[] items = {0, 10, 30, 2, 7, 5, 90, 76, 100, 45, 55};PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(3);MinMaxPriorityQueue<Integer> minMaxQueue =MinMaxPriorityQueue.orderedBy(Collections.reverseOrder()).maximumSize(3).create();for(Integer i : items) {minMaxQueue.add(i);}System.out.println("Items are : " + minMaxQueue); [100, 90, 76]2. Использование потокового API
Java Stream API — это отличная коллекция очень полезных методов, которые могут выполнять очень сложные задачи с помощью простых вызовов методов.
Чтобы найти первые N элементов в потоке, нам нужно отсортировать элементы в потоке и собрать три элемента из этого потока.
Integer[] items = {0, 10, 30, 2, 7, 5, 90, 76, 100, 45, 55};List<Integer> top3ItemsInList = Arrays.stream(items).sorted(Collections.reverseOrder()).limit(3).collect(Collectors.toList());System.out.println("Items are : " + top3ItemsInList); //[100, 90, 76]3. Массивы.copyOfRange()
API copyOfRange() копирует указанный диапазон заданного массива в новый массив. Так что если мы можем отсортировать массив, мы можем легко выбрать его первые 3 индекса элементов, поскольку они определенно будут верхними 3 элементами.
Integer[] items = {0, 10, 30, 2, 7, 5, 90, 76, 100, 45, 55};Arrays.sort(items, Collections.reverseOrder());Integer[] topThreeItems = Arrays.copyOfRange(items, 0, 3);System.out.println("Items are : " + Arrays.toString(topThreeItems)); //[100, 90, 76]4. Заключение
В этом уроке мы научились находить первые N элементов из массива. Первые N элементов могут быть N наибольшими элементами или N наименьшими элементами. Это зависит от варианта использования.
Мы научились находить элементы, используя Queues, Streams и функциональность копирования массива range. Мы можем построить больше подобных подходов в соответствии с нашими потребностями.
Обратите внимание, что только PriorityQueue не сортирует массив, в то время как все остальные решения работают с отсортированным массивом или поддерживают сортировку внутри. Поэтому, если вы хотите сохранить порядок верхних N элементов неизменным, как это было в исходном массиве, используйте PriorityQueue.