LeetCode 剑指 Offer 03. 数组中重复的数字
题目描述
题意分析
数组长度为
n，每个元素都在0..n-1的范围内，其中存在重复数字。只要返回任意一个重复值即可，不要求找出全部重复值，也不要求返回最小重复值或某个固定位置对应的值。值域与下标范围完全相同，是这道题的重要条件：每个数值都可以直接用作数组下标。下面利用这一点在原数组中记录哪些数已经出现，因此会修改数组的排列；如果必须保留输入，可以另用集合记录出现过的值，但需要
O(n)额外空间。
解法：原地下标归位
核心思路
[!blue]
把下标为
v的位置看作数值v应该占据的位置。若没有重复，所有数最终都可以放到对应下标；若一个数出现多次，就会有两个相同的数试图占用同一个位置，这种冲突正好用来判断重复。扫描到下标
i时，如果nums[i] == i，当前位置已经归位，直接前进。否则令target = nums[i]，准备把这个数放到下标target。此时target != i：如果目标位置已经有target，说明两个不同位置保存同一个数，可以直接返回它。如果目标位置还不是
target，就交换nums[i]与nums[target]，把当前数送到正确位置。换回下标i的数仍可能没有归位，所以必须留在当前下标继续检查，直到当前位置正确或发现冲突，不能交换一次就前进。每次真正交换，都会让目标位置从错误变成正确；已经正确的位置以后若再被同值指向，会直接触发判重，不会被换走。因此归位数量只增不减，最多进行线性次数的交换。两层循环并不意味着二次复杂度。
解题步骤
- 从左到右枚举下标
i。- 只要
nums[i] != i，就先保存target = nums[i]。- 若
nums[target] == target，当前位置与目标位置是两个不同下标，返回重复值target。- 否则交换
nums[i]与nums[target]，继续处理当前下标换入的数。- 当前下标归位后再前进。按题目存在重复的保证，会在判重分支返回；代码末尾的
-1表示遍历完仍未发现重复。
代码实现
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个位置，每次交换至少永久归位一个新位置，全部交换次数为O(n)。- 空间复杂度：
O(1)。只保存下标与交换用的临时变量，直接使用输入数组。
关键点总结
[!green]
- 值域恰好为下标范围，让数组本身可以承担数值到位置的记录功能。
- 判重时既要有目标槽位同值，也要保证当前数尚未归位，这样才对应两个不同位置。
- 每次交换都有不可逆的归位进展，既保证循环终止，也给出线性复杂度。
易错点总结
[!yellow]
- 套用从一开始的值域映射：本题数值从零开始，目标下标就是数值本身，不应减一。
- 不在
nums[i] != i的前提下判重：一个已经归位的数只是在与自身比较，不能据此认定重复。- 目标值相同仍继续交换：数组不会产生任何变化，内层循环将一直停留在同一状态，必须先返回。
- 交换一次就跳到下一位置：换入的值可能仍未归位，需要使用
while继续处理。- 赋值后再用变化的
nums[i]寻找目标：目标下标可能已经改变，应先保存target，再完成交换。- 忽略输入会被修改：原地方法复用了数组位置，依赖原顺序的调用方应改用不修改输入的记录方法。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 442. 数组中重复的数据 | 中等 | 同样用值域到下标映射记录出现，本题找任意重复值，原题返回全部重复值且下标偏移不同。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！