给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

    示例 1:
    输入: [1,3,4,2,2]
    输出: 2

    示例 2:
    输入: [3,1,3,4,2]
    输出: 3

    说明：
    不能更改原数组（假设数组是只读的）；
    只能使用额外的 O(1) 的空间；
    时间复杂度小于 O(n^2) ；
    数组中只有一个重复的数字，但它可能不止重复出现一次。

    方法1：二分查找

    // 分析：由于n+1长度的数字全部都为1到n之间。重复的数值肯定在1到n之间，然后1..n为一个有序的数组；
    // 我们可以对[1…n]之间的数组进行二分查找。
    // 方法：
    // 由于：mid = (1 + n) / 2，接下来判断最终答案是在 [1, mid] 中还是在 [mid + 1, n] 中；
    // 我们只需要统计原数组中小于等于 mid 的个数，记为 count；
    // 如果 count > mid ，鸽巢原理，在 [1,mid] 范围内的数字个数超过了 mid ，所以一定有一个重复数字；
    // 否则的话，既然不在 [1,mid] ，那么最终答案一定在 [mid + 1, n] 中；

    1. int findDuplicate(vector<int>& nums) 
    2. {
    3.     int n = nums.size() - 1;
    4.     int low = 1;
    5.     int high = n;
    6.     while(low < high)
    7.     {
    8.         int mid = (low + high) >> 1;
    9.         int cnt = 0;
    10.         for(int i=0; i<=n; ++i)
    11.         {
    12.             if (nums[i] <= mid) // 统计nums[]中数字不大于mid的个数
    13.             {
    14.                 ++cnt;
    15.             }
    16.         }
    17.         if (cnt > mid)         // 重复数字在[1...mid]之间
    18.         {
    19.             high = mid;
    20.         }
    21.         else                // 重复数字在[mid+1...n]之间
    22.         {
    23.             low = mid + 1;
    24.         }
    25.     }
    26.     return low;
    27. }

    方法2：快慢指针法

    // 分析：将数组的值看成next指针，数组的下标看成节点的索引。因为数组中至少有两个值一样，
    // 说明有两个节点指向同一位置，所以一定会出现环，然后有向环链表的入口点就是重复的数。
    // 然后这个问题可以参考快慢指针解决环链表入点问题；
    // 方法：使用快慢指针，同时从起点出发，慢指针一次走一步，快指针一次走两步，
    // 然后记录快慢指针相遇的点。然后再用两个指针，一个指针从起点出发，一个从相遇点出发，
    // 当再次相遇的时候就是入口点了。

    1. int findDuplicate(vector<int>& nums) 
    2. {
    3.     int slow = nums[0];
    4.     int fast = nums[nums[0]];
    5.     // 寻找相遇点
    6.     while (slow != fast)
    7.     {
    8.         slow = nums[slow];
    9.         fast = nums[nums[fast]];
    10.     }
    12.     // slow从起点出发，fast从相遇点出发，一次走一步
    13.     slow = 0;
    14.     while(slow != fast)
    15.     {
    16.         slow = nums[slow];
    17.         fast = nums[fast];
    18.     }
    19.     return slow;
    20. }

    欢迎交流，批评指正！