LeetCode 剑指 Offer 03. 数组中重复的数字

约 5 分钟
文章信息 13 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 20-50 字节跳动 微软 美团 快手 腾讯 虾皮 剑指 Offer 剑指 Offer（第 2 版）
标签
数组 哈希表 排序
目录

题目描述

✅ 剑指 Offer 03. 数组中重复的数字

image-20241107172223128

题意分析

给定一个长度为 $n$ 的数组，其中所有数字都在 $0$ 到 $n-1$ 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。要求找出数组中任意一个重复的数字。

「任意一个」这三个字放宽了要求：不需要找出全部重复项，也不需要找出重复次数最多的那个，只要返回一个确实出现了至少两次的数字即可。这意味着一旦发现冲突就可以立刻返回，不必扫完整个数组。

真正的关键约束信号是数值范围恰好等于下标范围：数组长度为 $n$，而元素取值落在 $[0, n-1]$，两者一一对应。题目专门把这个条件写进去，就是在暗示元素值本身可以当作下标使用——这是一个免费的、无需额外空间的映射通道。凡是看到「长度 $n$、值域 $[0, n-1]$」或「长度 $n$、值域 $[1, n]$」的组合，都应该立刻警觉。

由鸽巢原理，值域大小为 $n$ 而元素个数也是 $n$，只有当每个值恰好出现一次时才不存在重复；题目已说明存在重复，所以答案必然存在。

边界方面需要注意：数字 $0$ 是合法元素，任何「用 $0$ 表示未出现」的标记方案都会与真实数据混淆；另外若允许修改原数组是一个前置条件，题目对此没有禁止，但在面试中值得主动确认一句。

解法：原地下标归位

核心思路

数组长度为 $n$，元素值域恰好是 $[0,n-1]$，因此每个数字 v 都有唯一的目标位置：下标 v。若没有重复，最终一定能整理成 nums[i] == i 的排列；这比额外使用哈希表更充分地利用了题目条件。

遍历下标 i。当 nums[i] != i 时，令 v = nums[i]：

  • 若 nums[v] == v，说明值 v 已占据目标位置，而当前位置又出现一次 v，直接返回它。
  • 否则交换 nums[i] 与 nums[v]，把 v 放回目标位置，并继续处理交换到 i 的新值。

不变量是：外层指针走过的位置都已归位；每次交换至少新增一个归位位置，且归位位置若再次成为目标，只会触发重复判定而不会被换走。因此交换总次数是线性的，内层 while 不会造成 $O(n^2)$。

该方法达到 $O(1)$ 额外空间，但会修改输入数组。面试时应先确认是否允许修改；若不允许，可改用哈希表获得 $O(n)$ 时间和 $O(n)$ 空间。

解题步骤

  • 从左到右枚举下标 i，若 nums[i] == i，当前位置已经正确，直接继续。
  • 否则取 v = nums[i]，检查目标位置 nums[v]。
  • 若 nums[v] == v，返回 v，因为两个不同位置保存了同一个值。
  • 若目标位置未被 v 占据，交换 nums[i] 与 nums[v]，继续检查当前位置的新值。
  • 遍历结束仍未发现重复时返回 -1。

例如 [2, 3, 1, 0, 2, 5, 3]：在下标 0 连续归位 2、1、3、0 后，数组变为 [0, 1, 2, 3, 2, 5, 3]；走到下标 4 时，当前值和 nums[2] 都是 2，因此返回 2。

代码实现

class Solution {
    public int findRepeatNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] != i) {
                int target = nums[i];
                if (nums[target] == target) {
                    return target;
                }
                int temp = nums[i];
                nums[i] = nums[target];
                nums[target] = temp;
            }
        }
        return -1;
    }
}

func findRepeatNumber(nums []int) int {
    for i := range nums {
        for nums[i] != i {
            target := nums[i]
            if nums[target] == target {
                return target
            }
            nums[i], nums[target] = nums[target], nums[i]
        }
    }
    return -1
}

复杂度分析

  • 时间复杂度：$O(n)$。外层扫描 $n$ 个位置；每次交换至少让一个新位置归位，且归位状态不会回退，所以全程交换不超过 $n-1$ 次。
  • 空间复杂度：$O(1)$。只使用常数个变量，所有交换都在原数组中完成。

关键点总结

  • 「长度为 $n$、值域为 $[0,n-1]$」是把数值映射到下标的强提示。
  • 冲突发生在目标位置：nums[v] == v 且当前下标不是 v，即可确定 v 重复。
  • 交换后当前位置获得新值，必须继续归位，因此内层要用 while。
  • 线性复杂度的依据不是循环层数，而是每次交换都会永久增加至少一个归位位置。

易错点总结

  • 未确认输入值域便直接用 nums[i] 作为下标；本题有范围保证，工程复用时则需先校验。
  • 把 while 写成 if：一次交换后就前进，会留下尚未归位的新值。
  • 未先判重就直接交换：目标位置已是相同值时，交换不会改变数组，循环将无法结束。
  • 交换时覆盖了原值而没有使用临时变量；Go 的多重赋值可安全完成交换。
  • 忽略原地算法会修改输入；若调用方需要保留原数组，应改用哈希表或传入副本。

相似题目

题目 难度 考察点
41. 缺失的第一个正数 困难 同样是原地归位，但找的是缺失值且值域为 $[1, n]$
287. 寻找重复数 中等 明确禁止修改数组，需改用快慢指针做环入口检测
442. 数组中重复的数据 中等 要求找出全部重复项，适合用负号标记而非交换
448. 找到所有数组中消失的数字 简单 归位后收集所有未归位的下标，输出的是缺失集合
645. 错误的集合 简单 需同时定位重复值与缺失值，一次归位后两者一起读出