每天一道LeetCode-----给定大小为n+1的数组，元素大小在[1 : n]之间，只有一个元素会重复出现多次，找到重复的那个
Find the Duplicate Number
原题链接Find the Duplicate Number
给定一定大小为n+1的数组，数组中的元素只可能是1到n中的数字，包括1和n。在数组中，有一个数字重复了多次，找到这个数字。
要求不能改变源数组的值，空间复杂度为O(1)，时间复杂度要小于O(n2)。
注意数组中每个元素都只能是1到n之间的数字，这提供了一个有用的信息，即
- 对于每个元素，可以用它的大小和[1: n]之间的数字比较
什么意思呢，假设数组中只有n个元素，而每个元素的大小都在[1 : n]之间，且没有重复元素。那么对于1到n中的某个值w而言，整个数组中小于等于w的元素个数恰好等于w。可以通过先将数组排序后证明
接着，n个元素的时候恰好[1 : n]各一个，现在，随机从[1 : n]中选择一个数字添加到数组中，使数组元素个数变为n+1。此时，对于某个值w而言。如果添加的数字小于等于w，那么小于等于w的元素个数将大于w（因为添加前是等于w）。反之，如果添加的数字大于w，那么小于等于w的元素个数将小于w。
现在，假设数组元素个数为n+1，因为数组元素只有n中取值，所以数组中会有重复元素，可能重复多次。那么此时对于1到n+1中的某个值w而言，整个数组中小于等于w的元素个数就会有三种可能
-
数组中小于等于w的元素个数恰好等于w。这可以说明在数组所有元素中，值在[1 : w]这个范围内的元素没有重复，重复元素在[w + 1 : n]中。
- 证明，反证法。如果有重复元素，那么[w + 1 : n]这个范围内的元素将不会重复，那么数组中元素总个数为w + (n - w - 1 + 1) = n。而实际上数组元素个数为n+1，矛盾。
-
数组中小于等于w的元素个数小于w。这可以说明在数组所有元素中，值在[1 : w]这个范围内的元素没有重复，重复元素在[w + 1 : n]中。
- 证明，反证法。因为小于等于w的元素个数小于w，所以大于w的元素个数大于n + 1 - w。如果[w + 1 : n]没有重复元素，那么大于w的元素个数最多为n - w，矛盾。
-
数组中小于等于w的元素个数大于w。这可以说明在数组的所有元素中，重复元素在[1 : w]中。
- 证明，反证法。如果[1 : w]范围内没有重复的元素，那么小于等于w的元素个数最多为w，不可能大于w，矛盾。
通过这种划分，让上述w取当前区间的中值，就可以采用二分法找到重复的那个元素，代码如下
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int left = 1;
int right = nums.size();
while(left < right)
{
/* 取区间的中值作为w */
int middle = left + (right - left) / 2;
int count = 0;
/* 计算数组中所有小于等于w的元素个数 */
for(auto n : nums)
{
if(n <= middle)
++count;
}
/* 如果个数小于等于w，说明重复元素在[w+1 : n]的范围内 */
if(count <= middle)
left = middle + 1;
else
right = middle;
}
return left;
}
};其实仔细想一下，时间复杂度小于O(n2)的无非O(1)，O(lgn)，O(n)，O(nlgn)几种，又要求空间复杂度是O(1)，那么O(n)之前的几乎都没戏了，所以只可能是O(nlgn)。又因为O(lgn)通常和二分法联系在一起，所以很明显需要使用二分法。又因为数组元素在[1 : n]之间，所以可以用数组大小和下标作比较，即通过比较然后利用二分缩小范围。