Find the Duplicate Number

题目来源
找一个数组中重复的数字，size=n+1，数字范围1-n，不能用额外空间，不能改变原数组，时间复杂度小于O(N^2)，想了半天，只能用二分。
代码如下：

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        int l = 1, r = n - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            int smallOrEquals = 0;
            for (int i=0; i<n; i++)
                if (nums[i] <= mid)
                    smallOrEquals++;
            if (smallOrEquals > mid)
                r = mid;
            else
                l = mid + 1;
        }
        return l;
    }
};

还有O(N)的做法…完全想不到，类似于之前链表找循环的起始点，代码如下：

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = nums[0], fast = nums[nums[0]];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        int slow2 = 0;
        while (slow != slow2) {
            slow = nums[slow];
            slow2 = nums[slow2];
        }
        return slow;
    }
};