今天分享的題目來(lái)源于 LeetCode 第 287 號(hào)問(wèn)題：尋找重復(fù)數(shù)。

題目描述

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

示例 1:

輸入:?[1,3,4,2,2]
輸出:?2


示例 2:

輸入:?[3,1,3,4,2]
輸出:?3


說(shuō)明：

• 不能更改原數(shù)組（假設(shè)數(shù)組是只讀的）。

• 只能使用額外的 O(1) 的空間。

• 時(shí)間復(fù)雜度小于 O(n2) 。

• 數(shù)組中只有一個(gè)重復(fù)的數(shù)字，但它可能不止重復(fù)出現(xiàn)一次。

題目解析

給定一個(gè)整形數(shù)組，數(shù)組的長(zhǎng)度是 n + 1，數(shù)組里面存放的元素是區(qū)間 [1, n] 上的數(shù)，這個(gè)數(shù)組中有且僅有一個(gè)元素是重復(fù)的，題目讓我們找出這個(gè)元素，并且這道題給了如下的限制：

• 不能改變數(shù)組

• 只能使用 O(1) 的空間

• 時(shí)間復(fù)雜度必須小于 O(n^2)

• 重復(fù)的元素可重復(fù)多次

首先不能改變數(shù)組導(dǎo)致無(wú)法排序，也無(wú)法用 index 和元素建立關(guān)系；

只能使用 O(1) 的空間意味著使用哈希表去計(jì)數(shù)這條路也走不通；

時(shí)間復(fù)雜度必須小于 O(n^2) 表示暴力求解也不行；

重復(fù)的元素可重復(fù)多次 這一條加上后，本來(lái)可以通過(guò)累加求和然后做差 sum(array) - sum(1,2,...,n) 的方式也變得不可行。

本來(lái)是非常簡(jiǎn)單的一道數(shù)組遍歷的題目，加上了上面這四個(gè)條件后感覺(jué)有點(diǎn)無(wú)從下手。

我們說(shuō)做題要借助算法，而不是空想，因此對(duì)于這道題也不例外，我們可以問(wèn)自己這樣一個(gè)問(wèn)題，就是 “什么樣的算法可以不使用額外的空間解決數(shù)組上面的搜索問(wèn)題？”。

靜靜的思索一下。

你這時(shí)應(yīng)該隱隱約約知道了，難道是 二分查找！

什么？二分查找法？！

二分查找法不是對(duì)有序數(shù)組才適用么？

這里澄清一個(gè)誤區(qū)，二分法的使用 并不一定 需要在排序好的數(shù)組上面進(jìn)行，不要讓常見(jiàn)的例題限制了你的思路，二分法還有一個(gè)比較高級(jí)的用法叫做 按值二分。

這道題目交代的信息很少，我們只需要關(guān)注兩個(gè)東西 - 數(shù)組，數(shù)組里的元素，利用二分我們需要去思考的是，我們要找符合條件的元素作為答案，那么比答案小的元素具有什么樣的特質(zhì)，比答案大的元素又具有什么樣的特質(zhì)？，結(jié)合題目給我們的例子來(lái)看看：

（ 說(shuō)明：下面的 ?<= ?符號(hào)表明 小于或者等于。）

例1:

[1,3,4,2,2]?????????????????????????元素個(gè)數(shù)
<=?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


極端一點(diǎn)的例子 (必須保證數(shù)組的長(zhǎng)度是 n + 1, 并且元素都在區(qū)間[1,n] 上, 有且只有一個(gè)重復(fù))

[3,3,3,3,4]
<=?1?的元素：???????????????????????????0
<=?2?的元素：???????????????????????????0
<=?3?的元素：3,?3,?3,?3?????????????????4
<=?4?的元素：3,?3,?3,?3,?4??????????????5


看完上面幾個(gè)例子，相信你明白了一個(gè)事實(shí):

• “如果選中的數(shù) 小于 我們要找的答案，那么整個(gè)數(shù)組中小于或等于該數(shù)的元素個(gè)數(shù)必然小于或等于該元素的值;

• 如果選中的數(shù) 大于或等于 我們要找的答案，那么整個(gè)數(shù)組中小于或等于該數(shù)的元素個(gè)數(shù)必然 大于 該元素的值”

而且你可以看到，我們要找的答案其實(shí)就處于一個(gè)分界點(diǎn)的位置，尋找邊界值，這又是二分的一個(gè)應(yīng)用，而且題目已經(jīng)告訴我們數(shù)組里面的值只可能在 [1, n] 之間，這么一來(lái)，思路就是在 [1, n] 區(qū)間上做二分，然后按我們之前提到的邏輯去做分割。整個(gè)解法的時(shí)間復(fù)雜度是 O(nlogn)，也是滿(mǎn)足題目要求的。

上面的解法不是最優(yōu)的，但是個(gè)人覺(jué)得是根據(jù)現(xiàn)有的知識(shí)比較容易想到的。

另外一種 O(n) 的解法借鑒快慢指針找交點(diǎn)的思想，算法非常的巧妙，也非常的有趣，但不太容易想到，這里把代碼放上。

動(dòng)畫(huà)描述

代碼實(shí)現(xià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;
????}
}


代碼實(shí)現(xiàn)二

//快慢指針
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;
}