Java数组中查找Top K元素的高效实现方案

1. 概述

本文将深入探讨在 Java 数组中查找 Top K 最大元素 的多种实现方式。我们重点关注算法的时间复杂度，并使用 Big-O 表示法进行分析。这类问题在实际开发中非常常见，比如排行榜、热点数据提取等场景，踩坑也不少，值得系统梳理。

2. 暴力解法（Brute-Force）

最直观的思路是：循环 K 次，每次遍历数组找出最大值，移除后加入结果集。虽然逻辑清晰，但效率极低，属于典型的“能跑但别用”类型。

✅ 示例代码如下：

public List<Integer> findTopK(List<Integer> input, int k) {
    List<Integer> array = new ArrayList<>(input);
    List<Integer> 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;
}

⚠️ 时间复杂度为 **O(n × k)**，当 k 接近 n 时退化为 O(n²)，性能堪忧。且 ArrayList.remove() 是 O(n) 操作，进一步拉低效率。

3. 借助 Java 集合类的优化方案

Java Collections 提供了更高效的结构，我们可以借助它们优化性能。

3.1 使用 TreeSet

TreeSet 底层基于 红黑树（Red-Black Tree），天然有序，插入/删除操作时间复杂度为 O(log n)。

我们可以将所有元素加入 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)**，主要开销在构建 TreeSet。

❌ 但有个致命限制：TreeSet 不允许重复元素。如果输入数组包含重复值（如 [5, 3, 5, 2]），结果会丢失数据，因此该方案仅适用于去重场景。

3.2 使用 PriorityQueue（推荐）

PriorityQueue 在 Java 中是基于堆（Heap） 实现的优先队列。我们可以维护一个大小为 k 的最小堆（min-heap），遍历数组时：

将元素加入堆
若堆大小超过 k，则弹出堆顶（当前最小值）

最终堆中保留的就是最大的 k 个元素。

✅ 核心优势：

时间复杂度：**O(n log k)**，优于 TreeSet 方案
空间复杂度：O(k)，节省内存
支持重复元素

✅ 实现代码：

public List<Integer> findTopK(List<Integer> input, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    input.forEach(number -> {
        minHeap.add(number);

        if (minHeap.size() > k) {
            minHeap.poll(); // 弹出最小值
        }
    });

    List<Integer> topKList = new ArrayList<>(minHeap);
    Collections.sort(topKList, Collections.reverseOrder()); // 降序输出

    return topKList;
}

💡 注意：PriorityQueue 默认是最小堆。我们不需要手动反转，只需最后排序输出即可。也可以用 Collections.reverse()，但排序更直观。

✅ 这是实际项目中最推荐的方案，简单粗暴且高效。

4. 更优解：选择算法（Selection Algorithm）

如果你追求极致性能，可以了解 **快速选择算法（QuickSelect）**。

它基于快速排序的分区思想，平均时间复杂度可达 **O(n)**，最优解无疑。

但由于实现较复杂，且涉及 pivot 选择、边界处理等细节，调试成本高，在日常开发中使用频率较低。对于大多数场景，PriorityQueue 方案已完全够用。

5. 总结

方案	时间复杂度	是否支持重复	推荐指数
暴力解法	O(n×k)	✅	❌
TreeSet	O(n log n)	❌	⚠️
PriorityQueue	O(n log k)	✅	✅✅✅
快速选择	O(n)	✅	学术向

✅ 结论：

日常开发首选 PriorityQueue，兼顾性能与可读性
若数据无重复且 k 接近 n，可考虑 TreeSet
极致性能场景可研究 QuickSelect

示例代码已托管至 GitHub：https://github.com/baeldung/java-algorithms/tree/master/algorithms-miscellaneous-6

Persistence

REST

Security