Java性能面试题：海量整数列表Top3唯一值高效查找（分场景）

Hey there! Let's walk through this problem thoroughly—it's a classic test of how well you balance time and memory performance in Java. First, let's recap the requirements: we have an ArrayList of 1 million random integers (duplicates allowed), and we need to find the 3 largest unique values, optimized for two scenarios: time efficiency and memory efficiency.

为什么你的初始Stream方案不够优？ #

Your initial approach using stream().distinct().sorted().limit(3) works, but it's not optimal because:

• distinct() creates an intermediate collection to store unique values, adding memory overhead.
• sorted() runs in O(m log m) time (where m is the number of unique values). If most of the 1M integers are unique, this is way slower than necessary—we don't need to sort the entire dataset just to find the top 3!

场景1：时间受限（优先速度） #

For maximum speed, we need an O(n) single-pass solution with minimal overhead. The core idea is to track the top 3 unique values with variables, and use a small set to skip duplicates quickly.

实现代码 #

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Top3TimeOptimized {
    public static List<Integer> findTop3Unique(List<Integer> list) {
        int first = Integer.MIN_VALUE;
        int second = Integer.MIN_VALUE;
        int third = Integer.MIN_VALUE;
        Set<Integer> seenTopValues = new HashSet<>(3); // 固定容量节省内存

        for (int num : list) {
            // 跳过已经在Top3里的重复值
            if (seenTopValues.contains(num)) {
                continue;
            }

            // 更新Top3值
            if (num > first) {
                third = second;
                second = first;
                first = num;
                seenTopValues.add(num);
            } else if (num > second) {
                third = second;
                second = num;
                seenTopValues.add(num);
            } else if (num > third) {
                third = num;
                seenTopValues.add(num);
            }

            // 提前退出优化：当已经找到3个唯一值时，小于等于third的数直接跳过
            if (seenTopValues.size() == 3 && num <= third) {
                continue;
            }
        }

        // 收集结果（处理唯一值不足3个的情况）
        List<Integer> top3 = new ArrayList<>(3);
        if (first != Integer.MIN_VALUE) top3.add(first);
        if (second != Integer.MIN_VALUE && !top3.contains(second)) top3.add(second);
        if (third != Integer.MIN_VALUE && !top3.contains(third)) top3.add(third);

        return top3;
    }
}

优化点： #

• 用固定容量的HashSet做O(1)时间的重复检查，比每次对比三个变量快得多。
• 提前退出逻辑：一旦收集到3个唯一值，所有小于等于third的数直接跳过，减少无效比较。
• 没有中间集合（除了极小的HashSet）或排序操作，纯O(n)时间复杂度。

场景2：内存受限（优先节省内存） #

当内存紧张时，我们要消除所有额外开销。可以直接通过判断当前数是否属于已记录的Top3值来跳过重复，完全去掉HashSet。

实现代码 #

import java.util.ArrayList;
import java.util.List;

public class Top3MemoryOptimized {
    public static List<Integer> findTop3Unique(List<Integer> list) {
        int first = Integer.MIN_VALUE;
        int second = Integer.MIN_VALUE;
        int third = Integer.MIN_VALUE;

        for (int num : list) {
            // 跳过当前Top3里的重复值
            if (num == first || num == second || num == third) {
                continue;
            }

            // 更新Top3值
            if (num > first) {
                third = second;
                second = first;
                first = num;
            } else if (num > second) {
                third = second;
                second = num;
            } else if (num > third) {
                third = num;
            }
        }

        // 收集结果（处理边界情况）
        List<Integer> top3 = new ArrayList<>(3);
        if (first != Integer.MIN_VALUE) top3.add(first);
        if (second != Integer.MIN_VALUE && second != first) top3.add(second);
        if (third != Integer.MIN_VALUE && third != second) top3.add(third);

        return top3;
    }
}

优化点： #

• 仅用3个基本类型int变量，额外内存开销为O(1)（完全没有集合）。
• 仍然是O(n)时间复杂度，只是多了几次相等判断，用极小的时间代价换来了巨大的内存节省。
• 无需更换输入列表类型：ArrayList的连续存储比LinkedList的节点指针结构更节省内存。

性能优化学习思路 & 资源 #

要更好地应对这类问题，可以从以下方向入手：

1. 算法复杂度基础：吃透时间/空间复杂度（O(n)、O(n log n)等），理解为什么排序对Top K问题是过度操作。
2. Top K问题模式：学习标准解法（小K用变量跟踪，大K用堆，无序数据集用快速选择）。
3. Java集合性能：研究不同集合的开销（比如HashSet vs TreeSet、ArrayList vs LinkedList），选对工具。
4. JVM内存原理：了解Java对象的存储方式——基本类型变量比集合对象占用的内存少得多。
5. 实战练习：刷LeetCode的相关题目，比如215. 数组中的第K个最大元素，巩固这些概念。
6. 书籍推荐：《Java性能权威指南》深入讲解JVM优化、集合性能等内容，适合系统学习。

内容的提问来源于stack exchange，提问作者DarkKnight