LintCode 633. 寻找重复的数（这个题要复习）

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

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

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

class Solution {
public:
    int findDuplicate(vector<int> &nums) {
        int i = 0;
        while(nums[i] != nums[nums[i]])
            myswap(nums[i], nums[nums[i]]);
        return nums[i];
    }
    
    inline void myswap(int& a, int& b)
    {
        a ^= b ^= a ^= b;
    }
};

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

class Solution {
public:
    int findDuplicate(vector<int> &nums) {
        int idx, i;
        for(i = 0; i < nums.size(); ++i)
        {
            idx = abs(nums[i]);
            if(nums[idx] > 0)
                nums[idx] = -nums[idx];
            else
                return idx;
        }
        return -1;
    }
};