掬水月在手
弄花香满衣
C++，二分法。
二分法
二分法的思路相当暴力，复杂度应该是O(NlogN)。
用[left, right]表示该重复数字表示的范围，左闭右闭区间。
然后用int mid = (left + right) / 2 ，然后计算小于等于mid的元素个数cnt，如果cnt > mid，说明处于[1, mid]之间的元素个数要大于mid，所以就说明重复元素肯定小于等于mid，反之则大于mid，按情况缩小范围，直到范围内就一个元素。。。。
class Solution {
public:
int findDuplicate(vector<int> &nums) {
int left = 1, right = nums.size() - 1;
while (left < right) {
int mid = (left + right) / 2;
int cnt = 0;
for (int &it : nums)
if (it <= mid) cnt++;
if (cnt > mid)
right = mid;
else left = mid + 1;
}
return left;
}
};
负数标记（不符合题意，改变了原数组）
有个很巧妙的方法，O(N)的时间复杂度，O(1)的空间复杂度，第一次刷PAT见到这道题就是用的这种方法。
对于这个数组来说，每个元素nums[i]不仅可以记录第i+1个元素,还可以标记为i这个数被访问过，也就是记录两种信息。
怎么利用单个元素记录两种信息呢？
答：把遍历过的元素所在位置的值置为负数。
如果遍历到某个元素a，以该元素a的绝对值作为下标索引的值b是正数的话，将nums[i]置为相反的负数，是个负数的话，说明a被访问过了，那就直接返回a就好了。。。。
记住上面这句话，按照这句话写出代码，就能以“O(N)的时间复杂度，O(1)的空间复杂度”通过本题了。
class Solution {
public:
int findDuplicate(vector<int> &nums) {
int n = nums.size() - 1;
for (int i = 0; i <= n; i++) {
int a = nums[i];
if (a < 0) a = -a;
int b = nums[a];
if (b < 0) return a;
nums[a] = -b;
}
return -1;
}
};
