有一個長度是N+1的數組，數字範圍是1～N，其中有個數字出現了2次，其餘數字都出現了1次。求出現2次的數字是多少。
Python
方法一: 快慢指針法
以快慢指針來找到重複的數組值
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
slow, fast = nums[0], nums[nums[0]]
while slow != fast:
slow = nums[slow]
fast = nums[nums[fast]]
slow = 0
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return fast方法二 : Binary Search
如果i<=mid則計數+1，當count大於mid時，表示尾端等於mid，反之，start等於mid+1(重複數組在後面)
class Solution(object):
def findDuplicate(self, nums):
start = 1
end = len(nums) - 1
mid = int((start + end) / 2)
while start < end:
count = 0
for i in nums:
if i<=mid:
count += 1
if count>mid:
end = mid
else:
start = mid+1
mid = int((start+end)/2)
return start方法三 : sort
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
nums.sort()
for i in range(len(nums)-1):
if nums[i]==nums[i+1]:
return nums[i]C++
二分法
將數組中所有小於等於中間值的數的個數與中間值的大小比較，然後通過不斷縮小區間來找到重複的數。
初始化左指針 left 為 1，右指針 right 為 n。令 mid 為 left 和 right 的中間值。遍歷數組 nums，統計所有小於等於 mid 的數的個數 count。如果 count 大於 mid，說明重複的數在左區間，令 right = mid；否則，重複的數在右區間，令 left = mid + 1。重複步驟 2 到 4，直到 left 和 right 相等，此時的值即為重複的數
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int n = nums.size() - 1;
int left = 1, right = n;
while (left < right) {
int mid = (left + right) / 2;
int count = 0;
for (int num : nums) {
if (num <= mid) count++;
}
if (count > mid) right = mid;
else left = mid + 1;
}
return left;
}
};