LeetCode-287 尋找重復(fù)數(shù) 二分法

287. 尋找重復(fù)數(shù)

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

假設(shè) nums 只有 一個重復(fù)的整數(shù) ，找出 這個重復(fù)的數(shù) 。

你設(shè)計的解決方案必須不修改數(shù)組 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 中 只有一個整數(shù) 出現(xiàn) 兩次或多次 ，其余整數(shù)均只出現(xiàn) 一次

進階：

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

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

二分法

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

$i$12345

$cnt(i)$	1	2	4	5	6

根據(jù)上面提到的額外的條件，我們可以發(fā)現(xiàn)這樣一個規(guī)律：對于小于 target 的數(shù) i，$cnt(i)=i$?，對于大于等于 target 的數(shù) i，$cnt(i)>i$? 。因此，我們要找的重復(fù)數(shù) target，就是最小的使得 $cnt(i)>i$? 的數(shù)字 i?？梢钥吹?#xff0c;上例中 target 為3，當(dāng) $i<3$ 時，$cnt(i)=i$，當(dāng) $i\ge 3$ 時，$cnt(i)>i$。

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

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

常規(guī)二分法代碼（返回索引）：

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;} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode-287 寻找重复数 二分法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。