题目：
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Example 1:
Input: [1,3,4,2,2]
Output: 2
Example 2:
Input: [3,1,3,4,2]
Output: 3
Note:
- You must not modify the array (assume the array is read only).
- You must use only constant, O(1) extra space.
- Your runtime complexity should be less than O(n2).
- There is only one duplicate number in the array, but it could be repeated more than once.
代码：
方法一——二分法：
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int left = 1, right = nums.size()-1;
while (left < right){
int mid = left + (right - left) / 2, cnt = 0;
for (int num : nums) {
if (num <= mid) ++cnt;
}
if (cnt <= mid) left = mid + 1;
else right = mid;
}
return right;
}
};
方法二——双指针找环法：
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int slow = 0, fast = 0, t = 0;
while (true) {
slow = nums[slow];
fast = nums[nums[fast]];
if (slow == fast) break;
}
while (true) {
slow = nums[slow];
t = nums[t];
if (slow == t) break;
}
return slow;
}
};
方法三——位操作法：
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int res = 0, n = nums.size();
for (int i = 0; i < 32; ++i) {
int bit = (1 << i), cnt1 = 0, cnt2 = 0;
for (int k = 0; k < n; ++k) {
if ((k & bit) > 0) ++cnt1;
if ((nums[k] & bit) > 0) ++cnt2;
}
if (cnt2 > cnt1) res += bit;
}
return res;
}
};