給出一個(gè)數(shù)組 nums 包含 n + 1 個(gè)整數(shù)竭缝，每個(gè)整數(shù)是從 1 到 n (包括邊界)房维，保證至少存在一個(gè)重復(fù)的整數(shù)。假設(shè)只有一個(gè)重復(fù)的整數(shù)抬纸，找出這個(gè)重復(fù)的數(shù)咙俩。
注意事項(xiàng)
1.不能修改數(shù)組(假設(shè)數(shù)組只能讀)
2.只能用額外的O(1)的空間
3.時(shí)間復(fù)雜度小于O(n^2)
4.數(shù)組中只有一個(gè)重復(fù)的數(shù)，但可能重復(fù)超過一次
樣例
給出 nums = [5,5,4,3,2,1]湿故，返回 5.
給出 nums = [5,4,4,3,2,1]阿趁，返回 4.
思路
如果每個(gè)數(shù)只出現(xiàn)一次，那必然會(huì)有對(duì)于當(dāng)前數(shù) x坛猪，數(shù)組中小于 x 的數(shù)出現(xiàn)的總次數(shù)小于等于 x脖阵，所以一旦出現(xiàn)重復(fù)數(shù)就會(huì)使得對(duì)于當(dāng)前數(shù) y，數(shù)組中小于 y 的數(shù)出現(xiàn)的總次數(shù)大于 y墅茉，即構(gòu)成了二分條件
代碼
- 二分法
nlogn
public class Solution {
/**
* @param nums an array containing n + 1 integers which is between 1 and n
* @return the duplicate one
*/
public int findDuplicate(int[] nums) {
int start = 1;
int end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (check_smaller_num(mid, nums) <= mid) {
start = mid;
} else {
end = mid;
}
}
if (check_smaller_num(start, nums) <= start) {
return end;
}
return start;
}
public int check_smaller_num(int mid, int[] nums) {
int cnt = 0;
for (int i = 0; i < nums.length; i++){
if (nums[i] <= mid){
cnt++;
}
}
return cnt;
}
}
- 映射法
public class Solution {
/**
* @param nums an array containing n + 1 integers which is between 1 and n
* @return the duplicate one
*/
public int findDuplicate(int[] nums) {
// Write your code here
if (nums.length <= 1)
return -1;
int slow = nums[0];
int fast = nums[nums[0]];
while (slow != fast) {
slow = nums[slow];
fast = nums[nums[fast]];
}
fast = 0;
while (fast != slow) {
fast = nums[fast];
slow = nums[slow];
}
return slow;
}
}
