看了LeetCode上牛人的解答，感觉我的智商被碾压了~
原题
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.
给定一个包含n+1个整数的数组nums，该数组中的每个整数都在[1,n]的范围内，假设数组中只有一个数是重复的，找到那个重复的数。
Note|提示:
- You must not modify the array (assume the array is read only).| 不能改动数组内容
- You must use only constant, O(1) extra space.| 在O(1)的空间复杂度内完成
- Your runtime complexity should be less than
O(n2).| 时间复杂度不超过O(n^2) - There is only one duplicate number in the array, but it could be repeated more than once.| 只有一个重复数字，但是可能重复超过一次
思路1：O(nlogn)时间复杂度
英文版解释：https://leetcode.com/discuss/60830/solutions-explanation-space-without-changing-input-array
这个解法涉及到鸽巢原理。
假设有n=10的一个数组（大小是n+1），那我目前的搜索范围是[1,10]，先找中间的数mid=5.现在我们遍历数组的所有元素并统计<=5的元素个数，记作n_lteq5好了，那么有：
- 如果n_lteq5>5，那就有6个数字占了本来只有5个的坑位，那目标数字肯定是在[1,5]的范围内了；
- 如果n_lteq5<=5，那前面的元素都挺守规矩的，得看看[6,10]里头哪个数字在作怪；
这样每一次判断，问题的规模都会缩小一半，一共n+1个数字，时间复杂度是O(nlogn)
感觉碰到了很多二分思想的题目啊，关键点就是要找到一个什么划分方式把问题的规模缩小掉，而在这道题里头用到的就是鸽巢原理。
思路1代码
class Solution {
public:
int countLtEq(const vector<int>& nums, int n){
int count = 0;
for(int i=0; i<nums.size(); i++){
if(nums[i] <= n)
count ++;
}
return count;
}
int findDuplicate(vector<int>& nums) {
int n = nums.size() - 1;
int min = 1, max = n;
int mid;
int ltEqCnt;
while(min < max){
mid = (min + max)/2;
ltEqCnt = countLtEq(nums, mid);
if(ltEqCnt <= mid){
//[min, mid]是正常的，找另一边
min = mid+1;
} else {
max = mid;
}
}
return min; // min == max
}
};
插曲：如果可以改变数组元素呢？
感觉在剑指Offer上遇到过类似的题目。如果可以改变数组元素的话，可以按照下面的思路进行，时间复杂度是O(n)。基本思想是，一个萝卜一个坑，把搜索到的数放到自己应该在的位置上，比如1应该放在第一个位置上，如果后面再找到一个1，我们就会发现1这个位置的坑被前一个1占了，那就冲突了。
方便起见，数组的位置按1,2,3,…描述（而非0,1,2…）。假设有数组[5,4,2,3,1,5,6] ，当前工作的位置pos=1
- 先看第pos=1个数字5，在设想的排好序的序列里，5应该就在第5个位置上，因此我们把5和第5个位置上现有的数字1进行调换，结果就变成了[1,4,2,3,5,5,6] ；
- 看换回来的数字1，由于已经在1号位上，这次处理就结束了，往前挪一下，pos=2，看下一个数字；
- pos=2的数字是4，本来应该在4号位上，因此把4和4号位上的 3调换，数组变成[1,3,2,4,5,5,6] ；
- 这时候事情没完，因为换回来的3不在应该有的3号位上，因此把3和3号位上占着的2调换，数组变成[1,2,3,4,5,5,6] ；
- 换回的数字2是正确的位置，因此pos++，变成pos=3，类似地检查pos=4, 5发现都符合要求；
- 当pos=6时，此时位置上的元素是5，于是我们想把这个5归为到5号位，但是检查5号位的时候我们发现，上面已经有一个5了，这就说明5是重复数值了，搞定
可能有问，那如果原来的数组是[5,4,2,3,1,6,5] 呢？很显然，如果前面找到pos=6的时候都没发生冲突，那罪魁祸首肯定在最后个元素上面了。
这种方法只要遍历一次数组并做相应替换就行，除了会改变数组内容外，其他条件都满足，可惜啊。
思路2：O(n)时间复杂度
大神，大家快去膜拜：http://keithschwarz.com/interesting/code/?dir=find-duplicate
据说越是经典的代码行数越是写的简单，然而你并不能看懂…
似乎是把数组中的值看做单链表的next指针的值的，还在理解中~这个算法理论上是正确的。