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.
Example 1:
Input: [1,3,4,2,2]
Output: 2
Example 2:
Input: [3,1,3,4,2]
Output: 3
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.
- 解法一
/**
* Created by liuchaoqun01 on 2019/1/12.
*/
public class FindDuplicate {
/**
* 二分法查找
* @param nums
* @return
*/
public static int findDuplicate (int[] nums) {
// 这里left和right实际表示搜索范围
int left = 0;
int right = nums.length;
while (left < right) {
int mid = left + (right -left) / 2; // 正中间坐标计算方法
int cnt = 0;
for (int temp : nums) {
if (temp <= mid) {
++cnt; // 小于中间位置的数的个数
}
}
if (cnt > mid) {
right = mid; // 去小数那边查找, 注意这里因为是查找,因此不能落下mid
} else {
left = mid + 1; // 去大数那边查找
}
}
// 二分截止条件是left == right
return right;
}
public static void main(String[] args) {
int[] a = {3,1,3,4,2};
int b = findDuplicate(a);
System.out.println(b);
}
}
- 注意
今后所有的算法题目都会标注解法一，因为一道题目一定是有多种解法的，也有助于自己更新。
