287. 寻找重复数
题目描述
输入一个整数数组 nums，长度为 n + 1，每个元素都在 1 到 n 之间（含两端）。
数组里只有一个数是重复的，它可能出现两次，也可能出现更多次；其余的数都只出现一次。找出并返回这个重复的数。
要求不能修改 nums，并且只使用 O(1) 的额外空间。
示例 1
输入：nums = [1,3,4,2,2] 输出：2
解释：2 出现了两次。
示例 2
输入：nums = [3,1,3,4,2] 输出：3
解释：3 出现了两次。
示例 3
输入：nums = [3,3,3,3,3] 输出：3
解释：3 出现了五次。
数据范围
1 <= n <= 10^5nums.length == n + 11 <= nums[i] <= n- 只有一个整数出现了两次或更多次，其他整数各出现一次。
进阶：能否说明 nums 中为什么一定会有重复的数？能否设计出 O(n) 时间的算法？
解题思路：快慢指针（Floyd 判环）
把 nums 当作链表 next 指针，用 Floyd 快慢指针先找环内相遇点，再从起点和相遇点同步走找环入口。
为什么正确
数组映射形成的函数图必有环，重复值正是环的入口。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
fast 必须执行两次索引跳转；第二阶段重置的是 slow，不是 fast。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
from typing import List
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
slow = nums[0]
fast = nums[0]
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slowclass Solution {
public int findDuplicate(int[] nums) {
int slow = nums[0];
int fast = nums[0];
while (true) {
slow = nums[slow];
fast = nums[nums[fast]];
if (slow == fast)
break;
}
slow = nums[0];
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
}class Solution {
public:
int findDuplicate(vector<int>& nums) {
int slow = nums[0];
int fast = nums[0];
while (true) {
slow = nums[slow];
fast = nums[nums[fast]];
if (slow == fast)
break;
}
slow = nums[0];
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
};func findDuplicate(nums []int) int {
slow := nums[0]
fast := nums[0]
for {
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast {
break
}
}
slow = nums[0]
for slow != fast {
slow = nums[slow]
fast = nums[fast]
}
return slow
}var findDuplicate = function(nums) {
let slow = nums[0];
let fast = nums[0];
while (true) {
slow = nums[slow];
fast = nums[nums[fast]];
if (slow === fast)
break;
}
slow = nums[0];
while (slow !== fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
};function findDuplicate(nums: number[]): number {
let slow = nums[0];
let fast = nums[0];
while (true) {
slow = nums[slow];
fast = nums[nums[fast]];
if (slow === fast)
break;
}
slow = nums[0];
while (slow !== fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}其他解法
三种方法都满足不修改数组和 O(1) 空间。值域二分和逐位统计都是“计数比较”思想，O(n log n)；快慢指针把下标到值看成链表的 next 指针，重复数就是环的入口，达到 O(n)。
解法 2：在值域上二分 时间 O(n log n)，空间 O(1)
设 cnt(x) 为数组中 ≤ x 的元素个数。若重复数是 t，则 x < t 时 cnt(x) ≤ x，x ≥ t 时 cnt(x) > x，具有单调性。在 [1, n] 上二分，找第一个满足 cnt(x) > x 的 x，每次计算 cnt 需要扫一遍数组。
满足不修改数组、常数空间，正确性用抽屉原理就能说清。时间多一个 log。
from typing import List
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
lo, hi = 1, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
cnt = sum(1 for x in nums if x <= mid)
if cnt > mid:
hi = mid
else:
lo = mid + 1
return loclass Solution {
public int findDuplicate(int[] nums) {
int lo = 1, hi = nums.length - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
int cnt = 0;
for (int x : nums)
if (x <= mid) cnt++;
if (cnt > mid) hi = mid;
else lo = mid + 1;
}
return lo;
}
}class Solution {
public:
int findDuplicate(vector<int>& nums) {
int lo = 1, hi = nums.size() - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
int cnt = 0;
for (int x : nums)
if (x <= mid) cnt++;
if (cnt > mid) hi = mid;
else lo = mid + 1;
}
return lo;
}
};func findDuplicate(nums []int) int {
lo, hi := 1, len(nums)-1
for lo < hi {
mid := (lo + hi) / 2
cnt := 0
for _, x := range nums {
if x <= mid {
cnt++
}
}
if cnt > mid {
hi = mid
} else {
lo = mid + 1
}
}
return lo
}var findDuplicate = function(nums) {
let lo = 1, hi = nums.length - 1;
while (lo < hi) {
const mid = (lo + hi) >> 1;
let cnt = 0;
for (const x of nums)
if (x <= mid) cnt++;
if (cnt > mid) hi = mid;
else lo = mid + 1;
}
return lo;
};function findDuplicate(nums: number[]): number {
let lo = 1, hi = nums.length - 1;
while (lo < hi) {
const mid = (lo + hi) >> 1;
let cnt = 0;
for (const x of nums)
if (x <= mid) cnt++;
if (cnt > mid) hi = mid;
else lo = mid + 1;
}
return lo;
}解法 3：二进制逐位统计 时间 O(n log n)，空间 O(1)
对每一个二进制位 b，分别统计数组中这一位为 1 的个数 x 和 1..n 中这一位为 1 的个数 y。重复数在这一位为 1 当且仅当 x > y。把所有满足 x > y 的位拼起来就是答案。
同样不修改数组、常数空间，按位独立判断。要理解重复数出现多次、其他数缺失时这个比较仍然成立，推理略绕。
from typing import List
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
n = len(nums) - 1
ans = 0
for b in range(n.bit_length()):
mask = 1 << b
x = sum(1 for v in nums if v & mask)
y = sum(1 for i in range(1, n + 1) if i & mask)
if x > y:
ans |= mask
return ansclass Solution {
public int findDuplicate(int[] nums) {
int n = nums.length - 1, ans = 0;
for (int b = 0; (1 << b) <= n; b++) {
int mask = 1 << b, x = 0, y = 0;
for (int v : nums)
if ((v & mask) != 0) x++;
for (int i = 1; i <= n; i++)
if ((i & mask) != 0) y++;
if (x > y) ans |= mask;
}
return ans;
}
}class Solution {
public:
int findDuplicate(vector<int>& nums) {
int n = nums.size() - 1, ans = 0;
for (int b = 0; (1 << b) <= n; b++) {
int mask = 1 << b, x = 0, y = 0;
for (int v : nums)
if (v & mask) x++;
for (int i = 1; i <= n; i++)
if (i & mask) y++;
if (x > y) ans |= mask;
}
return ans;
}
};func findDuplicate(nums []int) int {
n, ans := len(nums)-1, 0
for b := 0; 1<<b <= n; b++ {
mask, x, y := 1<<b, 0, 0
for _, v := range nums {
if v&mask != 0 {
x++
}
}
for i := 1; i <= n; i++ {
if i&mask != 0 {
y++
}
}
if x > y {
ans |= mask
}
}
return ans
}var findDuplicate = function(nums) {
const n = nums.length - 1;
let ans = 0;
for (let b = 0; (1 << b) <= n; b++) {
const mask = 1 << b;
let x = 0, y = 0;
for (const v of nums)
if (v & mask) x++;
for (let i = 1; i <= n; i++)
if (i & mask) y++;
if (x > y) ans |= mask;
}
return ans;
};function findDuplicate(nums: number[]): number {
const n = nums.length - 1;
let ans = 0;
for (let b = 0; (1 << b) <= n; b++) {
const mask = 1 << b;
let x = 0, y = 0;
for (const v of nums)
if (v & mask) x++;
for (let i = 1; i <= n; i++)
if (i & mask) y++;
if (x > y) ans |= mask;
}
return ans;
}