作者：Sergei Golitsyn
链接：https://leetcode.com/problems/find-the-duplicate-number/
描述：
给定一个包含n + 1个整数的整数数字，其中每个整数在[1，n]包含范围内。
数字中只有一个重复的数字，返回此重复的数字。
您必须在不修改阵列数字并仅使用恒定额外空间的情况下解决问题。
`示例1：
输入：nums = [1,3,4,2,2]
输出：2
示例2：
输入：nums = [3,1,3,4,2]
输出：3`
解决方案：
好吧，大家好。让我们尝试解决这个问题。
我们知道我们有1到n的元素。
所有这些元素都是分类的。
如果
怎么办
我们将检查中间元素并计算元素的计数，较少
如果计数小于中间元素，则意味着我们在正确的部分中具有重复的元素。
例如：
[1,2,3,4,5,5,6]
mid = 4
foreach(1 : 6) -->
if (num <= cur){
count ++;
}
count = 1 (1)
...
count = 4 (4)
我们有4个，这就是为什么我们必须进入正确的部分。清楚吗？
然后，在正确的部分，我们可以做同样的事情。并向右移动或向左部分。
最后，我们将结果设置为中间元素，因为否则我们移至另一侧。
是的，这是一个修改后的二进制搜索。对于复杂问题，您似乎很简单。
确保您可以在数组上迭代，这将需要O（n）时间。在这种方法中，我们有O（log（n））时间复杂性，而没有其他内存。
下面的完整代码：
public int findDuplicate(int[] nums) {
int start = 1;
int end = nums.length - 1;
int rez = -1;
while(start <= end){
int cur = (end + start) / 2;
int count = 0;
for (int num : nums){
if (num <= cur){
count ++;
}
}
if (count > cur){
rez = cur;
end = cur - 1;
} else {
start = cur + 1;
}
}
return rez;
}