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.
思路
根据题意，题目给的是一个包含1到n+1的integer数组，其中不重复的数是（1-n）个，也就是说至少有2个数是重复。现在需要找出这个数来。
试想，给定一个数 m：
- 如果比 m 小的元素都没有重复的，在整个数组里面小于等于 m 元素的个数应该恰好为 m；
- 如果比 m 小的元素大于 m 个，那么很显然，重复的数字在 1 到 m 之间。
所以可以用二分法来做。
- 停止条件是
while(start <= end) - 先找mid（因为数是从
1 - n + 1， 所以mid就可以代表任意给定一个数m) - 遍历数组，在数组中找
nums[i] < mid的个数count。 - 如果
count > mid， 说明重复得数字一定出现在1- mid之间，更新end = mid -1; - 如果
count <= mid, 说明重复得数字一定出现在mid - end之间，更新start = mid + 1; - 最后返回
start即为重复的数。
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 == null || nums.length == 0) {
return 0;
}
int start = 1;
int end = nums.length;
int count = 0;
while (start <= end) {
int mid = start + (end - start) / 2;
count = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] <= mid) {
count++;
}
}
if (mid < count) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return start;
}
}
