資訊專欄INFORMATION COLUMN
摘要：如果的數(shù)字都只有一個，那么我們會形成一個閉合的環(huán)。如果有重復(fù)數(shù)字出現(xiàn)的話，如下這里就有一個的環(huán)，就是重復(fù)數(shù)字如果到每個數(shù)字都只出現(xiàn)一次，在里的個數(shù)應(yīng)該就是個數(shù)大于的話，前面的數(shù)字里就會有重復(fù)。
// 如果[1,n]的數(shù)字都只有一個，那么我們會形成一個閉合的環(huán)。
idx 1 2 3 4
val 3 1 4 2
1->3->4->2 這樣就是一個閉合的環(huán)。
如果有重復(fù)數(shù)字出現(xiàn)的話，如下：
idx 1 2 3 4 5
val 2 4 2 3 1
1->2->4->3->2->4 這里就有一個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每個數(shù)字都只出現(xiàn)一次，在nums里<=mid的個數(shù)應(yīng)該就是mid.
個數(shù)大于mid的話，前面的數(shù)字里就會有重復(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)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/67565.html
摘要：復(fù)雜度思路每次通過二分法找到一個值之后，搜索整個數(shù)組，觀察小于等于這個數(shù)的個數(shù)。考慮，小于這個位置的數(shù)的個數(shù)應(yīng)該是小于等于這個位置的。要做的就是像找中的環(huán)一樣，考慮重復(fù)的點在哪里?？紤]用快慢指針。代碼把一個指針放回到開頭的地方 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ù)，然后再遍歷整個數(shù)組看是否有跟這個數(shù)相同的數(shù)就行了。二分法復(fù)雜度時間空間思路實際上，我們可以根據(jù)抽屜原理簡化剛才的暴力法。 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...
閱讀 901·2021-11-22 12:04
閱讀 2106·2021-11-02 14:46
閱讀 626·2021-08-30 09:44
閱讀 2110·2019-08-30 15:54
閱讀 731·2019-08-29 13:48
閱讀 1598·2019-08-29 12:56
閱讀 3454·2019-08-28 17:51
閱讀 3290·2019-08-26 13:44
