資訊專(zhuān)欄INFORMATION COLUMN
摘要：如果的數(shù)字都只有一個(gè)，那么我們會(huì)形成一個(gè)閉合的環(huán)。如果有重復(fù)數(shù)字出現(xiàn)的話，如下這里就有一個(gè)的環(huán)，就是重復(fù)數(shù)字如果到每個(gè)數(shù)字都只出現(xiàn)一次，在里的個(gè)數(shù)應(yīng)該就是個(gè)數(shù)大于的話，前面的數(shù)字里就會(huì)有重復(fù)。
// 如果[1,n]的數(shù)字都只有一個(gè)，那么我們會(huì)形成一個(gè)閉合的環(huán)。
idx 1 2 3 4
val 3 1 4 2
1->3->4->2 這樣就是一個(gè)閉合的環(huán)。
如果有重復(fù)數(shù)字出現(xiàn)的話，如下：
idx 1 2 3 4 5
val 2 4 2 3 1
1->2->4->3->2->4 這里就有一個(gè)2->4->3->2的環(huán)， 2就是重復(fù)數(shù)字
public class Solution {
public int findDuplicate(int[] nums) {
int slow = nums[0];
int fast = nums[nums[0]];
while(slow != fast){
slow = nums[slow];
fast = nums[nums[fast]];
}
fast = 0;
while(slow != fast){
slow = nums[slow];
fast = nums[fast];
}
return fast;
}
}
如果1到mid每個(gè)數(shù)字都只出現(xiàn)一次，在nums里<=mid的個(gè)數(shù)應(yīng)該就是mid.
個(gè)數(shù)大于mid的話，前面的數(shù)字里就會(huì)有重復(fù)。
public class Solution {
public int findDuplicate(int[] nums) {
int n = nums.length-1, lo = 1, hi = n;
while(lo < hi){
int mid = lo + (hi-lo)/2, count = 0;
for(int n: nums)
if(n <= mid) count++;
if(count > mid) hi = mid;
else low = mid+1;
}
return lo;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/67565.html
摘要：復(fù)雜度思路每次通過(guò)二分法找到一個(gè)值之后，搜索整個(gè)數(shù)組，觀察小于等于這個(gè)數(shù)的個(gè)數(shù)?？紤]，小于這個(gè)位置的數(shù)的個(gè)數(shù)應(yīng)該是小于等于這個(gè)位置的。要做的就是像找中的環(huán)一樣，考慮重復(fù)的點(diǎn)在哪里?？紤]用快慢指針。代碼把一個(gè)指針?lè)呕氐介_(kāi)頭的地方 LeetCode[287] Find the Duplicate Number Given an array nums containing n + 1 in...
Problem Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate nu...
題目：Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number,...
摘要：暴力法復(fù)雜度時(shí)間空間思路如果不用空間的話，最直接的方法就是選擇一個(gè)數(shù)，然后再遍歷整個(gè)數(shù)組看是否有跟這個(gè)數(shù)相同的數(shù)就行了。二分法復(fù)雜度時(shí)間空間思路實(shí)際上，我們可以根據(jù)抽屜原理簡(jiǎn)化剛才的暴力法。 Find the Duplicate Number Given an array nums containing n + 1 integers where each integer is bet...
Problem Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate nu...
閱讀 968·2021-11-22 12:04
閱讀 2164·2021-11-02 14:46
閱讀 685·2021-08-30 09:44
閱讀 2158·2019-08-30 15:54
閱讀 790·2019-08-29 13:48
閱讀 1657·2019-08-29 12:56
閱讀 3522·2019-08-28 17:51
閱讀 3332·2019-08-26 13:44
