题目
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.
答案
class Solution {
public int findDuplicate(int[] nums) {
int l = 1, r = nums.length - 1;
while(l < r) {
int m = (l + r) / 2;
int cnt = 0;
for(int num : nums) {
if(num <= m) cnt++;
}
if(cnt > m) {
// Go left
r = m;
}
else {
l = m + 1;
}
}
return l;
}
}
