百万级整数List查找重复元素的最优时间复杂度实现方案咨询

嗨，这个场景太典型了！双循环的O(n²)复杂度在百万条数据面前完全是灾难——光是计算量就到了10¹²级别，根本跑不完。下面给你几个工业级的高效方案，按实用性排序：

1. 哈希集合（HashSet）法：时间O(n)，空间O(n) #

这是最常用的最优时间复杂度方案，利用哈希表的O(1)查找特性：

• 遍历列表时，每次检查当前元素是否在集合中
• 如果存在，说明是重复元素，直接收集
• 如果不存在，把元素加入集合

Java示例代码：

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

public class DuplicateFinder {
    public static List<Integer> findDuplicates(List<Integer> nums) {
        HashSet<Integer> seen = new HashSet<>();
        List<Integer> duplicates = new ArrayList<>();
        for (int num : nums) {
            if (!seen.add(num)) { // add返回false说明元素已存在
                duplicates.add(num);
            }
        }
        return duplicates;
    }
}

Python示例代码：

def find_duplicates(nums):
    seen = set()
    duplicates = []
    for num in nums:
        if num in seen:
            duplicates.append(num)
        else:
            seen.add(num)
    return duplicates

注意：如果需要去重后的重复元素列表（比如重复多次只保留一次），可以用另一个集合存重复元素，最后转成列表。

2. 排序后遍历：时间O(n log n)，空间O(1)（原地排序） #

如果内存比较紧张，不想用额外的O(n)空间，可以先排序再遍历：

• 排序后重复元素会相邻，只需要比较当前元素和前一个元素是否相等
• 优点是空间开销极小，缺点是会改变原列表的顺序，且排序的O(n log n)比哈希法慢一点，但百万数据依然很快

Java示例代码：

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

public class DuplicateFinder {
    public static List<Integer> findDuplicates(List<Integer> nums) {
        Collections.sort(nums);
        List<Integer> duplicates = new ArrayList<>();
        for (int i = 1; i < nums.size(); i++) {
            if (nums.get(i).equals(nums.get(i-1)) && 
                (duplicates.isEmpty() || !nums.get(i).equals(duplicates.get(duplicates.size()-1)))) {
                duplicates.add(nums.get(i));
            }
        }
        return duplicates;
    }
}

Python示例代码：

def find_duplicates(nums):
    nums.sort()
    duplicates = []
    for i in range(1, len(nums)):
        if nums[i] == nums[i-1] and (not duplicates or nums[i] != duplicates[-1]):
            duplicates.append(nums[i])
    return duplicates

3. 计数数组法：时间O(n)，空间O(k)（k为整数范围） #

如果已知整数的范围（比如所有数都是0~1000000），可以用计数数组直接统计出现次数，效率比哈希集合还高：

• 初始化一个长度为max_num+1的数组，初始值为0
• 遍历列表，每个元素对应的计数加1
• 最后遍历计数数组，收集计数>=2的元素

Java示例代码：

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

public class DuplicateFinder {
    public static List<Integer> findDuplicates(List<Integer> nums) {
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            if (num > max) max = num;
        }
        int[] count = new int[max + 1];
        List<Integer> duplicates = new ArrayList<>();
        for (int num : nums) {
            count[num]++;
        }
        for (int i = 0; i <= max; i++) {
            if (count[i] >= 2) {
                duplicates.add(i);
            }
        }
        return duplicates;
    }
}

方案选择建议 #

• 优先选哈希集合法：时间最优，实现简单，百万数据的内存开销完全可控（整数占4字节的话，百万个元素也就4MB左右）
• 内存紧张选排序法：牺牲一点时间换空间
• 整数范围明确选计数数组法：速度最快，空间开销最小

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