目錄
一，題目描述
英文描述
中文描述
二，解題思路
方法一：二分法
1）核心算法
2）複雜度證明
方法二：快慢指針
1）核心算法
2）複雜度證明
三，AC代碼
方法一：二分法
C++
Java
方法二：快慢指針
C++
Java
四，解題過程
方法一：二分法
第一搏
第二搏
方法二：快慢指針
第一搏
一，題目描述
原題連結287. 尋找重複數
英文描述
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one duplicate number in nums, return this duplicate number.
Follow-ups:
How can we prove that at least one duplicate number must exist in nums?
Can you solve the problem without modifying the array nums?
Can you solve the problem using only constant, O(1) extra space?
Can you solve the problem with runtime complexity less than O(n2)?
Example 1:
Input: nums = [1,3,4,2,2]
Output: 2
Example 2:
Input: nums = [3,1,3,4,2]
Output: 3
Example 3:
Input: nums = [1,1]
Output: 1
Example 4:
Input: nums = [1,1,2]
Output: 1
Constraints:
2 <= n <= 3 * 104
nums.length == n + 1
1 <= nums[i] <= n
All the integers in nums appear only once except for precisely one integer which appears two or more times.
中文描述
給定一個包含 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) 。
數組中隻有一個重複的數字，但它可能不止重複出現一次。
二，解題思路
方法一：二分法
1）核心算法
題目中給定了條件：
- 所有數字在[1，n-1]之内，n為數組長度；
- 隻有一個重複數字；
是以最終答案ans滿足兩個條件：
- 數組中出現小于ans的數字個數，小于ans本身；（多舉幾個數組試試就知道了）
- ans是滿足條件1的最後一個數字；
接下來就可以根據上面ans的條件進行二分查找了：
- 根據左右邊界确定mid，查找數組中小于mid的數字個數cnt；（小于等于的話需要調整邊界更新條件、ans更新位置）
- cnt<mid：left = mid + 1，ans = mid（記錄可能是答案的數字）；
- cnt>=mid：right = mid - 1；
2）複雜度證明
時間複雜度: O(nlogn), 其中n為nums[]數組的長度。二分查找最多需要二分O(logn) 次，每次判斷的時候需要O(n)周遊nums[]數組求解小于mid的數的個數，是以總時間複雜度為O(n log n)。
空間複雜度: O(1)。 我們隻需要常數空間存放若幹變量。
方法二：快慢指針
1）核心算法
非常巧妙的借助了數學思路：
我們對nums[]數組建圖，每個位置i連一條i→nums[i]的邊。由于存在的重複的數字target, 是以target這個位置一定有起碼兩條指向它的邊， 是以整張圖一定存在環，且我們要找到的target 就是這個環的入口。
裡面有幾個關鍵問題：
1，為什麼target這個位置一定有起碼兩條指向它的邊？
題目條件是，隻有一個重複的數，是以至少有兩個位置i、j，使得nums[i] == nums[j] == target，即i → target、j → target。
2，為什麼一定存在環？
正向推導有點麻煩，可以考慮什麼條件下不存在環。
首先，由于數組中的數字都是[1，n]，數組大小為n+1，是以從位置0出發建構的圖一定不會再回到0；
從0出發路徑上的節點有兩個選擇：
（這就是為什麼選擇從0開始）
- 選擇路徑内的節點作為下個節點；（這樣就構成了環）
- 選擇路徑外的節點作為下個節點；（這樣可以不斷擴充從0出發的聯通圖）
要想不構成環，有兩點需要注意：
- 在從0出發構成的連通圖中，位置i 和 nums[i]不相同（若相同的話，i→nums[i]自身 ，且由于是聯通圖，是以另外至少一條邊也連着nums[i]，這樣就構成了環）；
- 假設該聯通圖中有6個點，每個點都有對應的一條邊，那麼共有6條邊，然而6個點構成的連線如果不存在環的話，最多隻能有5條邊，那多出來的那條邊指向哪裡了呢？當然是指向我們的答案了o(*￣▽￣*)ブ
是以條件不成立，圖中一定有環！
3，為什麼target就是環的入口呢？
從0出發的聯通圖中必定有環，而且沒有一個節點指向0，那麼看圖應該很清楚了吧。
4，怎麼找環的入口？
我們先設定慢指針slow和快指針fast，慢指針每次走一步，快指針每次走兩步。根據（Floyd判圈算法）兩指針在有環的情況下一定會相遇， 此時我們再樣slow放置起點0，兩個指針每次同時移動一步，相遇點就是答案。（圖源 @力扣）
很優雅的數學證明(☆▽☆)
2）複雜度證明
時間複雜度：O(n)。「Floyd 判圈算法」時間複雜度為線性的時間複雜度。
空間複雜度：O(1)。我們隻需要常數空間存放若幹變量。
三，AC代碼
方法一：二分法
C++
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int left = 1, right = nums.size() - 1, ans = 0;
while(left <= right){ // !!!這裡需要改為等于 否則ans不會更新
int mid = (left + right) >> 1;
int smallNum = 0;
for(int i = 0; i < nums.size(); i++){
smallNum += (nums[i] < mid) ? 1 : 0;
}
if(smallNum < mid){
left = mid + 1;
ans = mid;
}
else right = mid - 1;
}
return ans;
}
}; Java
class Solution {
public int findDuplicate(int[] nums) {
int left = 1, right = nums.length - 1, ans = 0;
while(left <= right) {
int mid = (left + right) >> 1;
int cnt = 0;
for(int x : nums){
cnt += (x < mid) ? 1 : 0;
}
if(cnt < mid) {
left = mid + 1;
ans = mid;
} else {
right = mid - 1;
}
}
return ans;
}
} 方法二：快慢指針
C++
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int fast = 0, slow = 0;
// 階段一：尋找相遇點
do{
fast = nums[nums[fast]];// 雙重索引相當于走兩步
slow = nums[slow];
} while(slow != fast);
slow = 0;
// 階段二：尋找環入口
while(nums[slow] != nums[fast]){
slow = nums[slow];
fast = nums[fast];
}
return nums[fast];
}
}; Java
class Solution {
public int findDuplicate(int[] nums) {
int slow = 0, fast = 0;
do{
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
slow = 0;
while(nums[slow] != nums[fast]) {
slow = nums[slow];
fast = nums[fast];
}
return nums[slow];
}
} 四，解題過程
參考：@力扣官方題解【尋找重複數】
按照題目要求，時間O(N^2)以内，空間O(1)，原數組隻讀，着實想不出辦法，果斷向解題區大佬求助。◑﹏◐
看懂大緻思路後自己敲了一遍，并且對比高效題解進行一步步的修改，記錄如下：（隻測試了二分法和快慢指針，二進制那個方法操作太高端，沒敢看）
方法一：二分法
第一搏
由于是尋找滿足條件1（數組中出現小于ans的數字個數，小于ans本身）的最後一個數字，也就是說即使mid為ans時，如果不能确定mid為最後一個符合此條件的數字，盲目的left = mid + 1 / right = mid - 1，那麼很有可能在邊界劃分時，與答案失之交臂。
是以加上了repeatNum來記錄數字的重複次數，并優先判斷其是否大于1 ，以此決定算法是否終止。
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int left = 1, right = nums.size() - 1;
while(left < right){
int mid = (left + right) >> 1;
int smallNum = 0, repeatNum = 0;
for(int i = 0; i < nums.size(); i++){
smallNum += (nums[i] < mid) ? 1 : 0;
repeatNum += (nums[i] == mid) ? 1 : 0;
}
if(repeatNum > 1) return mid;
if(smallNum < mid) left = mid + 1;
else right = mid - 1;
}
return left;
}
}; 第二搏
其實上面的做法是不斷打更新檔，擠出來的，确實不優雅。
欣賞了官方題解後才恍然大悟。o(*￣▽￣*)ブ
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int left = 1, right = nums.size() - 1, ans = 0;
while(left <= right){ // !!!這裡需要改為等于 否則ans不會更新
int mid = (left + right) >> 1;
int smallNum = 0;
for(int i = 0; i < nums.size(); i++){
smallNum += (nums[i] < mid) ? 1 : 0;
}
if(smallNum < mid){
left = mid + 1;
ans = mid;
}
else right = mid - 1;
}
return ans;
}
};