題目鏈接：傳送門

題目描述:

給定一個數組 nums 包含 n + 1 個整數，每個整數在 1 到 n 之間，包括 1 和 n。現在假設數組中存在一個重復的數字，找到該重復的數字。

注意

不能修改數組元素，假設數組是只讀的。

僅可以使用常數即O(1)O(1)的額外空間。

時間復雜度需要低于O(n2)O(n2)。

數組中僅有一個重復數字，但它可能重復超過1次。

樣例

Example 1:

Input: [1,3,4,2,2]

Output: 2

Example 2:

Input: [3,1,3,4,2]
Output: 3

算法
(雙指針移動) O(n)
因為每個數都是 1 到 n，所以此題可以當做Linked List Cycle II來處理。
首先first和second指針均為0，然后first每次前進一格，second每次前進兩格。i前進一格在這里指的是nums[i]。剩余部分請參考Linked List Cycle II中的算法證明。
時間復雜度
參見Linked List Cycle II時間復雜度部分，整個數組僅遍歷常數次，故時間復雜度為O(n)。

作者：wzc1995
鏈接：https://www.acwing.com/solution/LeetCode/content/302/

---

?

將數組轉化為鏈表形式：數組 [1,3,4,2,2]

current / index	0	1	2	3	4
next / num[index]	1	3	4	2	2

?

index為當前值的索引，num[index]為下個一值的索引next index。上表中的數組表示成鏈表如下圖，方框中為index, num[index]

?

利用【142_環形鏈表 II】的方法，找到環入口，即為重復數字

設：

　　slow指針移動速度為1，fast指針移動速度為2；slow指針在環內移動（非環部分）長度為a，slow指針在環內移動長度為b

　　兩指針相遇時候，slow指針移動距離為a+b，fast指針移動距離為2(a+b)，可知兩指針距離差a+b即為整數倍的環長

　　從head移動a的距離為入環點；由2可知從head開始移動a+(a+b)的距離也為入環點，即將A點繼續移動距離a則可到達入環點

　　將slow指針移動回head，同時同速移動兩個指針，相遇點即為入環點

說明：

　　因為數組中不含0，所以不會因為index = 0, num[0] = 0導致死循環；對于其他位置index = num[index]，若該值重復則會自身成環，若無重復則不會被遍歷到

作者：LuoRong1994
鏈接：https://leetcode-cn.com/problems/two-sum/solution/287_xun-zhao-zhong-fu-shu-by-user9081a/

---

?

1 class Solution { 2 public: 3 int findDuplicate(vector<int>& nums) { 4 int cnt = 0 ; 5 int L = 1 , R = nums.size() - 1 , Mid , ans = 0 ; 6 while ( L < R ) { 7 Mid = (L+R) >> 1; 8 cnt = 0 ; 9 for ( int x : nums ) 10 cnt += L <= x && x <= Mid ; 11 if ( Mid - L + 1 < cnt ){ 12 R = Mid ; 13 }else { 14 L = Mid + 1 ; 15 } 16 } 17 return R ; 18 19 } 20 }; 二分做法

?

1 class Solution { 2 public: 3 int findDuplicate(vector<int>& nums) { 4 int Fir , Sec ; 5 Fir = Sec = 0 ; 6 do{ 7 Fir = nums[Fir] ; 8 Sec = nums[nums[Sec]] ; 9 }while ( Fir != Sec ); 10 11 Fir = 0; 12 while ( Fir != Sec ){ 13 Fir = nums[Fir] ; 14 Sec = nums[Sec] ; 15 } 16 return Fir; 17 } 18 }; 雙指針

?

轉載于:https://www.cnblogs.com/Osea/p/11182305.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【leetcode】287. 寻找重复数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。