如何高效查找数组中首个重复出现的元素-js教程-PHP中文网

如何高效查找数组中首个重复出现的元素

本文介绍多种优化方案来查找数组中“第二个出现位置最靠前”的重复元素，重点对比时间复杂度为 o(n²) 的暴力解法与 o(n) 的哈希集合解法，并提供可读性强、符合工程实践的现代 javascript 实现。

本文介绍多种优化方案来查找数组中“第二个出现位置最靠前”的重复元素，重点对比时间复杂度为 o(n²) 的暴力解法与 o(n) 的哈希集合解法，并提供可读性强、符合工程实践的现代 javascript 实现。

在处理如玩具厂 ID 校验这类实际场景时，关键需求并非“任意重复数”，而是首个发生重复的数——即其第二次出现的索引最小。例如在 [2, 1, 3, 5, 3, 2] 中，3 的第二次出现位于索引 4，而 2 的第二次出现在索引 5，因此正确答案是 3。

你提供的嵌套循环解法逻辑正确，但时间复杂度为 O(n²)，在大数据量下性能较差。更优解法应利用「空间换时间」思想，通过一次遍历配合哈希结构记录已见元素：

✅ 推荐解法：Set + 单次遍历（O(n) 时间，O(n) 空间）

function findFirstRepeated(gifts) {
  const seen = new Set();
  for (const id of gifts) {
    if (seen.has(id)) {
      return id; // 第一个被发现已存在过的元素，即其第二次出现位置最早
    }
    seen.add(id);
  }
  return -1; // 无重复
}

该解法核心逻辑简洁有力：遇到第一个“已在集合中存在”的元素，立即返回——它必然是题目定义的“首个重复数”。因为遍历顺序是从左到右，我们总在该数第二次出现的瞬间捕获它，而此时尚未遇到任何其他数的第二次出现。

⚠️ 注意事项与边界验证

Set.prototype.has() 和 add() 均为平均 O(1) 操作，整段代码稳定 O(n)；
不依赖 == 或 === 的隐式类型转换，Set 使用 SameValueZero 比较，对 0 和 -0、NaN 等特殊值行为明确（本题 ID 为数字，通常无需额外处理）；
若输入为空数组或无重复，函数正确返回 -1，与题目要求完全一致。

? 对比原解法的改进点

维度	原双重循环解法	Set 单次遍历解法
时间复杂度	O(n²) —— 最坏需比较 n²/2 次	O(n) —— 严格单次扫描
空间复杂度	O(1)	O(n) —— 最多存储全部不重复元素
可读性	嵌套逻辑易出错，意图隐晦	行为直白：“见过了？→ 返回；否则记下”
扩展性	难以适配去重、统计等衍生需求	易扩展（如改用 Map 记录首次索引）

? 进阶提示：若需返回重复位置信息

当调试或日志需要知道“在哪次索引重复”时，可升级为 Map 存储首次出现索引：

function findFirstRepeatedWithIndex(gifts) {
  const firstIndex = new Map();
  for (let i = 0; i <p>综上，使用 <code>Set</code> 的单次遍历方案是兼顾性能、可读性与健壮性的最佳实践。它不仅满足 Advent.js Day 1 的所有测试用例，更是处理类似“首次重复”问题的标准范式。</p>