LeetCode-287 尋找重復數 二分法

287. 尋找重復數

給定一個包含 n + 1 個整數的數組 nums ，其數字都在 1 到 n 之間（包括 1 和 n），可知至少存在一個重復的整數。

假設 nums 只有 一個重復的整數 ，找出 這個重復的數 。

你設計的解決方案必須不修改數組 nums 且只用常量級 O(1) 的額外空間。

示例 1：

輸入：nums = [1,3,4,2,2]
輸出：2
示例 2：

輸入：nums = [3,1,3,4,2]
輸出：3
示例 3：

輸入：nums = [1,1]
輸出：1
示例 4：

輸入：nums = [1,1,2]
輸出：1

提示：

1 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n
nums 中 只有一個整數 出現 兩次或多次 ，其余整數均只出現 一次

進階：

如何證明 nums 中至少存在一個重復的數字?
你可以設計一個線性級時間復雜度 O(n) 的解決方案嗎？

對于尋找重復數這種題，常規做法的話如哈希都可以做，但是本題的要求是不修改數組 nums 且只用常量級 O(1) 的額外空間。注意到本題給出了一個常規尋找重復數題目沒有的條件：其數字都在 1 到 n 之間（包括 1 和 n）

二分法

記要找的重復數為 target，$cnt(i)$ 表示給定數組 $nums$ 中不大于 $i$ 的數字個數。比如 $cnt(3)$ 就是 $nums$ 中1, 2, 3的個數之和，顯然 $cnt(i)$ 是遞增的。以數組 {1, 2, 3, 3, 4 ,5} 為例：

$i$	1	2	3	4	5
$cnt(i)$	1	2	4	5	6

根據上面提到的額外的條件，我們可以發現這樣一個規律：對于小于 target 的數 i，$cnt(i)=i$?，對于大于等于 target 的數 i，$cnt(i)>i$? 。因此，我們要找的重復數 target，就是最小的使得 $cnt(i)>i$? 的數字 i。可以看到，上例中 target 為3，當 $i<3$ 時，$cnt(i)=i$，當 $i\ge 3$ 時，$cnt(i)>i$。

而我們回顧以下常規的二分法，是這樣的：對于一個遞增（有序）的序列 $nums$ 和 給定值 target，我們要找到最小的使得 $nums[i]>target$ 的數字 i。

這就是這個題為什么可以使用二分法，遞增序列當然是使用二分法的前提，我們用 $cnt(i)$ 來合理地構造；然后根據具體的要找的條件來更新結果就好了。

常規二分法代碼（返回索引）：

int bin_search(vector<int>& nums, int target) {int n = nums.size();int l = 0, r = n-1;int mid;while (l<=r) {mid = (l+r) >> 1;if (nums[mid] < target) l = mid + 1;else if (nums[mid] > target)r = mid - 1;elsebreak;}return mid;
}

本題代碼（C++）：

class Solution {
public:int findDuplicate(vector<int>& nums) {int n = nums.size();int l = 0, r = n-1, ans = -1;while (l<=r) {int mid = (l+r) >> 1;int cnt = 0;for (int i=0; i<n; ++i) {				// 計算cnt(mid)，這里的mid就是我們上面公式中的icnt += nums[i] <= mid ? 1 : 0;}if (cnt<=mid) {				// 比較cnt(mid)和midl = mid + 1;}else {								// 若cnt(mid)>mid，則mid有可能是target：所有滿足cnt(mid)>mid的值中最小的mid值即為target（即代碼中的ans）ans = mid;r = mid - 1;}}return ans;}
};

雙指針

我們將數組轉換為鏈表，即將下標 $n$ 和數 $nums[n]$ 建立一個映射關系 f(n)，將 $n$ 作為下一個元素 $f(n)$ 的志向。數組元素的取值范圍在 $[1,n]$ 之間，而數組長度為 $n+1$ ，所以按照數組元素取值一定不可能越界。然后利用鏈表判環的快慢指針方法找到相同元素。

詳見：https://leetcode.cn/problems/find-the-duplicate-number/solution/287xun-zhao-zhong-fu-shu-by-kirsche/

class Solution {
public:int findDuplicate(vector<int>& nums) {int fast = 0, slow = 0;while (true) {fast = nums[nums[fast]];slow = nums[slow];if (slow == fast) break;}fast = 0;while (true) {slow = nums[slow];fast = nums[fast];if (slow == fast) return fast;}}
};