数组中的重复数字

问题

在一个长度为 n 的数组中，所有数字都在 0 到 n-1 的范围内。找出数组中任意一个重复的数字。

示例：

• 输入：[2, 3, 1, 0, 2, 5, 3]
• 输出：2 或 3（返回任意一个重复数字即可）

解答

方法一：哈希表

function findDuplicate(nums) {
  const seen = new Set();
  
  for (const num of nums) {
    // 如果已存在，说明是重复数字
    if (seen.has(num)) {
      return num;
    }
    seen.add(num);
  }
  
  return -1; // 没有重复
}

// 测试
console.log(findDuplicate([2, 3, 1, 0, 2, 5, 3])); // 2

时间复杂度 O(n)，空间复杂度 O(n)。

方法二：原地交换

利用数字范围是 0 到 n-1 的特点，将每个数字放到对应下标位置。

function findDuplicate(nums) {
  for (let i = 0; i < nums.length; i++) {
    // 当前数字不在正确位置时，尝试交换
    while (nums[i] !== i) {
      const target = nums[i];
      
      // 目标位置已有相同数字，找到重复
      if (nums[target] === target) {
        return target;
      }
      
      // 交换到正确位置
      [nums[i], nums[target]] = [nums[target], nums[i]];
    }
  }
  
  return -1;
}

// 测试
console.log(findDuplicate([2, 3, 1, 0, 2, 5, 3])); // 2

时间复杂度 O(n)，空间复杂度 O(1)。

方法三：排序

function findDuplicate(nums) {
  nums.sort((a, b) => a - b);
  
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] === nums[i - 1]) {
      return nums[i];
    }
  }
  
  return -1;
}

// 测试
console.log(findDuplicate([2, 3, 1, 0, 2, 5, 3])); // 2

时间复杂度 O(n log n)，空间复杂度 O(1)，但会修改原数组。

关键点

• 哈希表是最直观的解法，用空间换时间
• 原地交换利用了”数字范围 0 到 n-1”的条件，实现 O(1) 空间
• 原地交换的核心：数字 x 应该放在下标 x 的位置
• 排序方法简单但会改变原数组顺序
• 面试时优先考虑原地交换，展示对问题特性的利用