如何高效查找数组重复元素?能否用Java集合实现低迭代低复杂度?
首先明确理论优化边界:要准确检测数组中的重复元素,至少需要遍历一次未提前判定重复的元素,任何低于O(n)平均时间复杂度的方法,要么依赖元素取值范围的特殊约定,要么是概率性检测,不具备通用准确性。优化的核心方向是把遍历轮次压到最低,尽可能减少单元素的操作开销,支持找到重复后直接提前终止遍历。
针对低迭代次数要求,最优的遍历方式是边扫描边判定的单轮遍历,完全可以通过Java集合类实现符合要求的低开销重复查找。
通用场景(元素取值无固定范围)的最优实现
没有特殊取值约束的通用场景下,基于HashSet的单轮扫描法是效率最高的方案:
- 迭代次数:最多完成1次全数组遍历,找到重复元素后直接终止,不需要遍历剩余元素
- 时间复杂度:平均O(n),每个元素的哈希查找、插入操作平均为O(1)
- 空间复杂度:O(k),k为数组中不重复元素的数量
实现时不要分开写contains判断+add操作,直接利用HashSet.add()的返回值(元素已存在时返回false),单元素只需要做一次哈希计算,操作开销直接减半。大数组场景下可以提前根据数组长度设置哈希表初始容量(按数组长度/0.75的比例设置),避免哈希表扩容带来的额外拷贝开销。
示例Java代码:
import java.util.HashSet; import java.util.Set; public class DuplicateDetector { public static Integer getFirstDuplicate(int[] data) { Set<Integer> visited = new HashSet<>(data.length / 0.75); for (int item : data) { // add返回false代表元素已经存在 if (!visited.add(item)) { return item; } } return null; } }
特殊取值范围场景的零额外空间优化
如果题目明确约束:数组内的元素都是正整数,且取值范围严格在[1, 数组长度n]区间内,可以用原地标记的方法,完全不需要额外集合空间,依然保持单轮遍历的效率:
- 迭代次数:最多1次全数组遍历
- 时间复杂度:O(n)
- 空间复杂度:O(1)
实现逻辑是把原数组本身作为标记表:遍历每个元素时,取元素的绝对值作为下标,将对应下标的数组值置为负数代表“该值已经出现过”;如果遍历到某个元素时,发现对应下标的值已经是负数,就说明当前元素是重复值。
示例Java代码:
public static int getRangeRestrictedDuplicate(int[] nums) { for (int i = 0; i < nums.length; i++) { int targetIdx = Math.abs(nums[i]); if (nums[targetIdx] < 0) { return targetIdx; } nums[targetIdx] = -nums[targetIdx]; } return -1; }
注意:这个方法会修改原数组内容,如果业务不允许修改原数据结构,还是要回到HashSet的方案。
不推荐的低效实现
以下方法的迭代次数、时间复杂度都达不到最优要求,大数组场景下性能损耗明显:
- 双重嵌套循环逐元素比对:时间复杂度O(n²),迭代次数随数组长度平方增长,万级以上元素就会出现明显卡顿
- 先排序再比对相邻元素:排序本身的时间复杂度是O(nlogn),还需要额外一轮遍历,总开销远高于哈希表方案,仅在后续需要使用排序后数组的场景下考虑
- 调用集合工具类的
frequency、distinct等封装方法:这类方法内部会进行多轮遍历,还会生成额外的中间集合,且不支持找到第一个重复元素就提前终止,性能比手动实现的边遍历边判定方案差。
内容的提问来源于stack exchange,提问作者Narasimha

