今天分享的題目來源于 LeetCode 第 287 號問題：尋找重復數，
題目描述
給定一個包含 n + 1 個整數的陣列 nums，其數字都在 1 到 n 之間（包括 1 和 n），可知至少存在一個重復的整數，假設只有一個重復的整數，找出這個重復的數，
示例 1:
輸入: [1,3,4,2,2]
輸出: 2
示例 2:
輸入: [3,1,3,4,2]
輸出: 3
說明：
- 不能更改原陣列（假設陣列是只讀的），
- 只能使用額外的 O(1) 的空間，
- 時間復雜度小于 O(n2) ，
- 陣列中只有一個重復的數字，但它可能不止重復出現一次，
題目決議
個人博客：www.cxyxiaowu.com
給定一個整形陣列，陣列的長度是 n + 1，陣列里面存放的元素是區間 [1, n] 上的數，這個陣列中有且僅有一個元素是重復的，題目讓我們找出這個元素，并且這道題給了如下的限制：
- 不能改變陣列
- 只能使用 O(1) 的空間
- 時間復雜度必須小于 O(n^2)
- 重復的元素可重復多次
首先不能改變陣列導致無法排序，也無法用 index 和元素建立關系；
只能使用 O(1) 的空間意味著使用哈希表去計數這條路也走不通；
時間復雜度必須小于 O(n^2) 表示暴力求解也不行；
重復的元素可重復多次 這一條加上后，本來可以通過累加求和然后做差 sum(array) - sum(1,2,...,n) 的方式也變得不可行，
本來是非常簡單的一道陣列遍歷的題目，加上了上面這四個條件后感覺有點無從下手，
我們說做題要借助演算法，而不是空想，因此對于這道題也不例外，我們可以問自己這樣一個問題，就是 “什么樣的演算法可以不使用額外的空間解決陣列上面的搜索問題？”，
靜靜的思索一下，
你這時應該隱隱約約知道了，難道是 二分查找！
什么？二分查找法？！
二分查找法不是對有序陣列才適用么？
這里澄清一個誤區，二分法的使用 并不一定 需要在排序好的陣列上面進行，不要讓常見的例題限制了你的思路，二分法還有一個比較高級的用法叫做 按值二分，
這道題目交代的資訊很少，我們只需要關注兩個東西 - 陣列，陣列里的元素，利用二分我們需要去思考的是，我們要找符合條件的元素作為答案，那么比答案小的元素具有什么樣的特質，比答案大的元素又具有什么樣的特質？，結合題目給我們的例子來看看：
（ 說明：下面的 <= 符號表明 小于或者等于，）
例1:
[1,3,4,2,2] 元素個數
<= 1 的元素：1 1
<= 2 的元素：1, 2, 2 3
<= 3 的元素：1, 2, 2, 3 4
<= 4 的元素：1, 2, 2, 3, 4 5
例2:
[3,1,3,4,2]
<= 1 的元素：1 1
<= 2 的元素：1, 2 2
<= 3 的元素：1, 2, 3, 3 4
<= 4 的元素：1, 2, 3, 3, 4 5
極端一點的例子 (必須保證陣列的長度是 n + 1, 并且元素都在區間[1,n] 上, 有且只有一個重復)
[3,3,3,3,4]
<= 1 的元素： 0
<= 2 的元素： 0
<= 3 的元素：3, 3, 3, 3 4
<= 4 的元素：3, 3, 3, 3, 4 5
看完上面幾個例子，相信你明白了一個事實:
-
“如果選中的數 小于 我們要找的答案，那么整個陣列中小于或等于該數的元素個數必然小于或等于該元素的值;
-
如果選中的數 大于或等于 我們要找的答案，那么整個陣列中小于或等于該數的元素個數必然 大于 該元素的值”
而且你可以看到，我們要找的答案其實就處于一個分界點的位置，尋找邊界值，這又是二分的一個應用，而且題目已經告訴我們陣列里面的值只可能在 [1, n] 之間，這么一來，思路就是在 [1, n] 區間上做二分，然后按我們之前提到的邏輯去做分割，整個解法的時間復雜度是 O(nlogn)，也是滿足題目要求的，
上面的解法不是最優的，但是個人覺得是根據現有的知識比較容易想到的，
另外一種 O(n) 的解法借鑒快慢指標找交點的思想，演算法非常的巧妙，也非常的有趣，但不太容易想到，這里把代碼放上，
代碼實作一
//二分查找
class Solution {
public int findDuplicate(int[] nums) {
int len = nums.length;
int start = 1;
int end = len - 1;
while (start < end) {
int mid = start + (end - start) / 2;
int counter = 0;
for (int num:nums) {
if (num <= mid) {
counter++;
}
}
if (counter > mid) {
end = mid;
} else {
start = mid + 1;
}
}
return start;
}
}
代碼實作二
//快慢指標
public int findDuplicate(int[] nums) {
int fast = nums[nums[0]];
int slow = nums[0];
while (fast != slow) {
fast = nums[nums[fast]];
slow = nums[slow];
}
slow = 0;
while (fast != slow) {
fast = nums[fast];
slow = nums[slow];
}
return slow;
}
?? 看完三件事：
如果你覺得這篇內容對你挺有啟發，我想邀請你幫我三個忙：
- 點贊，讓更多的人也能看到這篇內容（收藏不點贊，都是耍流氓 -_-）
- 關注我和專欄，讓我們成為長期關系
- 關注公眾號「五分鐘學演算法」，第一時間閱讀最新的演算法文章，公眾號后臺回復 1024 送你 50 本 演算法編程書籍，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/138807.html
標籤：其他
上一篇：Cracking the coding interview目錄及資料收集
下一篇：C語言字串之無重復字符的最長子串