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, 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.
Solution 1: Use binary search for number count. Give a range, [lo,hi], if the duplicate number is within the range, counter>hi-lo. It is O(nlogn) complexity
public class Solution {
public int findDuplicate(int[] nums) {
int n=nums.length-1;
int lo=1, hi=n;
while (lo<hi) {
int mid=lo+(hi-lo)/2;
if (count(nums,lo,mid)>mid-lo+1) hi=mid;
else lo=mid+1;
}
return lo;
}
private int count(int[] nums, int lo, int hi) {
int res=0;
for (int x: nums) {
if (x>=lo && x<=hi) res++;
}
return res;
}
}
没有评论:
发表评论