問題描述
來源：LeetCode第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中只有一個整數出現兩次或多次，其餘整數均只出現一次
二分法解決
找出重複數字，這題有兩個限制條件，一個就是不能修改原數組，一個是使用O（1）的額外空間。有了這兩個限制條件，那麼通過排序再查找這種方式是行不通了。
這題我們可以使用二分法進行查找，一般使用二分法的時候數組必須是有序的，但這題數組是無序，不過沒關係。這裡使用二分法的兩個指針指向的不是數組中的元素，而是一個有序的區間。使用二分法之前我們首先要搞懂什麼是抽屜原理。
桌上有十個蘋果，要把這十個蘋果放到九個抽屜里，無論怎樣放，我們會發現至少會有一個抽屜裡面放不少於兩個蘋果。這一現象就是我們所說的「抽屜原理」。
對於這道題我們使用兩個指針，一個指向最小值1，一個指向最大值nums.length-1，每次我們取這兩個指針的中間值mid，然後統計數組中小於等於mid元素的個數count。
如果count大於mid，根據抽屜原理，重複數字肯定小於等於mid，我們縮小兩指針的範圍。舉個例子：比如小於等於5的個數是6，也就是說6個蘋果放到5個抽屜中，那麼至少有一個抽屜不少於兩個蘋果。
如果count不大於mid，那麼重複數字肯定是大於mid的。這種情況下是不適合抽屜原理的，比如把3個蘋果放到5個抽屜中，也有可能某個抽屜的蘋果數不少於兩個。但這題說了是n+1個元素，只有一個是重複的，也就是說前面3個蘋果放到5個抽屜中不可能某個抽屜的蘋果數大於1。這裡以示例一為例來畫個圖看一下
--------------------------------------------
--------------------------------------------
來看下代碼
●624，給表達式添加運算符（回溯算法解決）
●607，位運算等多種方式判斷是否存在重複元素
●449，快慢指針解決環形鍊表
●460. 快慢指針解環形鍊表 II
截止到目前我已經寫了600多道算法題了，為了方便大家閱讀，我把部分算法題整理成了pdf文檔，目前有1000多頁，大家可以在下面公眾號「數據結構和算法」中回復關鍵字「pdf」即可獲取下載鏈接。
留言列表