資訊專(zhuān)欄INFORMATION COLUMN
摘要：復(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
Binary SearchGiven 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, find the duplicate one.
Note:
You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
復(fù)雜度
O(NlgN), O(1)
思路
每次通過(guò)二分法找到一個(gè)值之后，搜索整個(gè)數(shù)組，觀察小于等于這個(gè)數(shù)的個(gè)數(shù)。
考慮[1,2,3,2]，小于這個(gè)位置的數(shù)的個(gè)數(shù)應(yīng)該是小于等于這個(gè)位置的。如果cnt > mid,說(shuō)明在小于這個(gè)位置的數(shù)的范圍內(nèi)，存在duplicate，right = mid - 1;
代碼
public int findDuplicate(int[] nums) {
int left = 0, right = nums.length - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
int cnt = 0;
for(int i = 0; i < nums.length; i ++) {
if(nums[i] <= mid) cnt ++;
}
if(cnt > mid) right = mid - 1;
else left = mid + 1;
}
return left;
}
LinkedList判斷循環(huán)
復(fù)雜度
O(N), O(1)
思路
考慮一定會(huì)有duplicate出現(xiàn)，說(shuō)明，數(shù)組里面的值組成了一個(gè)環(huán)，如果考慮像linkedlist那樣。
要做的就是像找linkedlist中的環(huán)一樣，考慮重復(fù)的點(diǎn)在哪里。
考慮用快慢指針。
代碼
public int findDuplicate(int[] nums) {
if(nums.length > 1) {
int slow = 0;
int fast = 0;
while(true) {
slow = nums[slow];
fast = nums[nums[fast]];
if(slow == fast) {
// case like [1,2,3,1]
// 把一個(gè)指針?lè)呕氐介_(kāi)頭的地方
slow = 0;
while(slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
}
}
return -1;
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65263.html
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,...
摘要：如果的數(shù)字都只有一個(gè)，那么我們會(huì)形成一個(gè)閉合的環(huán)。如果有重復(fù)數(shù)字出現(xiàn)的話(huà)，如下這里就有一個(gè)的環(huán)，就是重復(fù)數(shù)字如果到每個(gè)數(shù)字都只出現(xiàn)一次，在里的個(gè)數(shù)應(yīng)該就是個(gè)數(shù)大于的話(huà)，前面的數(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)的話(huà)，如下：...
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...
摘要：暴力法復(fù)雜度時(shí)間空間思路如果不用空間的話(huà)，最直接的方法就是選擇一個(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...
閱讀 2638·2021-11-02 14:39
閱讀 4369·2021-10-11 10:58
閱讀 1505·2021-09-06 15:12
閱讀 1890·2021-09-01 10:49
閱讀 1365·2019-08-29 18:31
閱讀 1904·2019-08-29 16:10
閱讀 3377·2019-08-28 18:21
閱讀 906·2019-08-26 10:42
