题意
解一
二分答案
简单解释，官解也很详细。
定义：dp[i] 表示nums[i] 中 < = i 的数的个数。
看这样一个序列：
nums：3 1 3 4 2
dp： 1 2 4 5
性质：自重复的数起，之后所有dp[i] 都 >i ，之前都 <=i。
在看这样一个序列：
nums：3 1 3 4 3
dp： 1 1 4 5
尽管重复了多次，但是还是满足上面的性质。
那么我们二分答案，统计<=mid 的数的个数，如果个数>mid ，说明是在右侧，可能是答案，r=mid，否则l=mid+1。
class Solution { public: int findDuplicate(vector<int>& nums) { int n = nums.size(); int l = 1, r = n; while(l < r) { int mid = (l + r) >> 1; auto f = [=](int x){ int res = 0; for (int i = 0; i < n; i++) if(nums[i] <= x) res += 1; return res <= x; }; if(f(mid)) l = mid + 1; else r = mid; } return r; } }; /* 一旦加上了重复的数，那么之后一定更大 // 二分check，更小就不要，说明在答案左，l向右调整。 nums: 1 3 2 4 2 [1234]: 1 3 4 5 mid: 3 -> res = 4, r = 3 mid: 2 -> res = 3, r = 2 mid: 1 -> res = 1, l = 2 l == r = 2 nums: 1 3 2 3 4 3 [1234]: 1 2 5 6 mid: 3 -> res = 5, r = 3 mid: 2 -> res = 2, l = 3 l == r = 3 */
解二
二进制
重复一次：
重复的数为x，[1,n] 都各出现一次，外加x 多出现一次。
统计二进制下 1 的个数，原序列相比[1,n] 序列，多出的 1 都是由 x产生。
重复多次：
重复的数为 x ，x 代替 [1,n] 中没出现的数 y ，外加 x多出现一次。
四种情况：00、01、10、11（以下x，y表示某一位为1或0）
x=0,y=0：<=
x=0,y=1：<=
y=0x=1,y=0：>
x=1,y=1：>
所以，对于 > 的情况，将该位 1 加上即可。
class Solution { public: int findDuplicate(vector<int>& nums) { int n = nums.size(); int res = 0; for (int i = 0; i < 31; i++) { int x = 0, y = 0; for (int j = 0; j < n; j++) { if(nums[j] & (1 << i)) x += 1; } for (int j = 1; j < n; j++) { if(j & (1 << i)) y += 1; } if(x > y) res |= (1 << i); } return res; } };
解三
快慢指针
n+1个数，[1,n] 范围内。每个位置 i 连边 i−>nums[i]。
3 1 3 4 2
0 1 2 3 4
建边：0->3, 1->1, 2->3, 3->4, 4->2
明显重复的 3 是环的入口。
又点 0 只可能有出边，不可能自环。所以定义快慢指针 l , r都从 0开始。
然后就是环形链表找入口的常规解法：
慢一步、快二步
慢置为 0 00
慢一步、快一步
class Solution { public: int findDuplicate(vector<int>& nums) { int l = 0, r = 0; do { l = nums[l]; r = nums[nums[r]]; } while(l != r); l = 0; while(l != r) { l = nums[l]; r = nums[r]; } return l; } };
