class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        //吧每个数都放到正确的位置上，如果nums[i] != i说明nums[i]为重复元素
        if(nums.empty()) return -1;
        int n = nums.size();
        for(auto x:nums)
           if(x < 0 || x >= n) return -1;
        for(int i = 0;i < n;++i){
            while(nums[i] != nums[nums[i]]) swap(nums[nums[i]],nums[i]);
            if(nums[i] != i) return nums[i];
        }
        return -1;

        /*
        //普通解法，开一个数组记录那些元素出现过，最后返回未出现的元素时间空间都是On,
        if(nums.empty()) return -1;
        int n = nums.size();
        for(auto x:nums)
           if(x < 0 || x >= n) return -1;
        //cout << n << endl;
        vector<bool > st(n,false);

        for(auto x:nums)
            //if(x < 0 || x >= n) return -1;//
            //注意，这个测试中有任意一个违法数字都是输出-1的。故而违法判断应该在开头
            else{
                if(st[x]) return x;
                st[x] = true;
            }


        return -1;*/
    }
};