«1. Обзор
В этом руководстве мы реализуем различные решения проблемы нахождения k самых больших элементов в массиве с помощью Java. Для описания временной сложности мы будем использовать нотацию Big-O.
2. Решение грубой силы
Решение этой проблемы методом грубой силы заключается в переборе заданного массива k раз. На каждой итерации мы найдем наибольшее значение. Затем мы удалим это значение из массива и поместим в выходной список:
public List findTopK(List input, int k) {
List array = new ArrayList<>(input);
List topKList = new ArrayList<>();
for (int i = 0; i < k; i++) {
int maxIndex = 0;
for (int j = 1; j < array.size(); j++) {
if (array.get(j) > array.get(maxIndex)) {
maxIndex = j;
}
}
topKList.add(array.remove(maxIndex));
}
return topKList;
}
Если мы предположим, что n — это размер данного массива, временная сложность этого решения равна O(n * k). Кроме того, это самое неэффективное решение.
3. Подход с использованием коллекций Java
Однако существуют более эффективные решения этой проблемы. В этом разделе мы объясним два из них с использованием коллекций Java.
3.1. TreeSet
TreeSet имеет структуру данных красно-черного дерева в качестве основы. В результате добавление значения в этот набор стоит O(log n). TreeSet — это отсортированная коллекция. Следовательно, мы можем поместить все значения в TreeSet и извлечь первые k из них:
public List<Integer> findTopK(List<Integer> input, int k) {
Set<Integer> sortedSet = new TreeSet<>(Comparator.reverseOrder());
sortedSet.addAll(input);
return sortedSet.stream().limit(k).collect(Collectors.toList());
}
Временная сложность этого решения составляет O(n * log n). Прежде всего, это должно быть более эффективным, чем метод грубой силы, если k ≤ log n.
Важно помнить, что TreeSet не содержит дубликатов. В результате решение работает только для входного массива с различными значениями.
3.2. PriorityQueue
PriorityQueue — это структура данных кучи в Java. С его помощью мы можем получить решение O(n * log k). Более того, это будет более быстрое решение, чем предыдущее. Из-за указанной проблемы k всегда меньше размера массива. Итак, это означает, что O(n * log k) ≥ O (n * log n).
Алгоритм проходит один раз по заданному массиву. На каждой итерации мы будем добавлять новый элемент в кучу. Кроме того, мы сохраним размер кучи меньше или равным k. Итак, нам придется удалить лишние элементы из кучи и добавить новые. В результате после перебора массива в куче останется k самых больших значений:
public List<Integer> findTopK(List<Integer> input, int k) {
PriorityQueue<Integer> maxHeap = new PriorityQueue<>();
input.forEach(number -> {
maxHeap.add(number);
if (maxHeap.size() > k) {
maxHeap.poll();
}
});
List<Integer> topKList = new ArrayList<>(maxHeap);
Collections.reverse(topKList);
return topKList;
}
4. Алгоритм выбора
Существует множество подходов к решению данной задачи. И, хотя это выходит за рамки данного руководства, использование подхода алгоритма выбора будет лучшим, поскольку он дает линейную временную сложность.
5. Заключение
В этом уроке мы описали несколько решений для поиска k самых больших элементов в массиве.
Как обычно, код примера доступен на GitHub.