我的LeetCode：https://leetcode-cn.com/u/ituring/
我的LeetCode刷題原始碼[GitHub]：https://github.com/izhoujie/Algorithmcii
LeetCode 287. 尋找重復數
題目
給定一個包含 n + 1 個整數的陣列 nums，其數字都在 1 到 n 之間（包括 1 和 n），可知至少存在一個重復的整數，假設只有一個重復的整數，找出這個重復的數，
示例 1:
輸入: [1,3,4,2,2]
輸出: 2
示例 2:
輸入: [3,1,3,4,2]
輸出: 3
說明：
- 不能更改原陣列（假設陣列是只讀的），
- 只能使用額外的 $ {\color{Magenta}{\Omicron\left(1\right)}} $ 的空間，
- 時間復雜度小于 $ {\color{Magenta}{\Omicron\left(n^{2}\right)}} $) ，
- 陣列中只有一個重復的數字，但它可能不止重復出現一次，
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/find-the-duplicate-number
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
解題思路
思路1-把陣列看成有環的鏈表，尋找環的入口
如果把鏈表看做是有環的鏈表，那么環的入口就是重復的那個數；
根據題意，陣列的值范圍為[1, n]，而陣列的長度為n+1，所以用任意陣列的值作為下標都不存在越界的問題；
尋找環可以用快慢指標來進行，圖解如下：
圖中有幾個關鍵資訊：
- 快慢指標的起始位置:頭節點；
- 快慢指標的相遇位置：相遇點；
- 環的入口即重復的數位置：環入口；
步驟：
- 快慢指標，慢指標每次走1步，快指標每次走2步；
- 兩指標相遇后，將快指標重置為頭結點，然后兩指標同步每次均移動1步直至相遇，此時的節點即為環的入口（重復的數）；
決議：
快慢指標首次相遇的點必在環中（任意一點），假設快指標在環中轉了n圈(很顯然，n至少為1，不然無法相遇)再加a部分，根據運動長度，快指標是慢指標的兩倍，則有：
即：
\[F = (n - 1) * (a + b) + b \]忽略掉\((n - 1) * (a + b)\)的部分，重復的整個環不影響分析，那么就可以得到：
\[F = b \]所以，在相遇后，重置其中一個指標為頭結點，兩個指標一個走F部分長度，一個走b部分長度，最終必會在環的入口節點相遇，也就找到了重復的數；
演算法復雜度:
- 時間復雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $ 對陣列進行了少量遍歷
- 空間復雜度： $ {\color{Magenta}{\Omicron\left(1\right)}} $
演算法原始碼示例
package leetcode;
/**
* @author ZhouJie
* @date 2020年5月31日 下午2:58:54
* @Description: 287. 尋找重復數
*
*/
public class LeetCode_0287 {
}
class Solution_0287 {
/**
* @author: ZhouJie
* @date: 2020年5月31日 下午2:59:24
* @param: @param nums
* @param: @return
* @return: int
* @Description: 1-將陣列看作有環鏈表，使用快慢指標尋找環入口；
*
*/
public int findDuplicate_1(int[] nums) {
int fast = 0, slow = 0;
while (true) {
fast = nums[nums[fast]];
slow = nums[slow];
// 此時找到了環內的一個同步節點，然后重置其中一個指標為頭節點，開始尋找環入口
if (fast == slow) {
fast = 0;
while (nums[fast] != nums[slow]) {
fast = nums[fast];
slow = nums[slow];
}
return nums[fast];
}
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/177273.html
標籤：Java
上一篇：Java桌面應用程式打包
下一篇：Java - IO - 位元組流