You need to enable JavaScript to run this app. 如何高效查找数组重复元素?能否用Java集合实现低迭代低复杂度?
优惠活动
大模型
产品
解决方案
定价
更多

如何高效查找数组重复元素?能否用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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.12 13:15:09