/*采用"元素置换"的方法--元素和nums[元素]需相同
例：枚举当前元素为4
查看数组nums中第4个位置上的元素是否为4：若为4，则说明出现重复元素；若不为4，则将当前元素与该位置元素进行交换
对交换后的元素重复上述操作
------------------
时间复杂度：o(n)
空间复杂度：o(1) -- 此为本算法的最大优点
*/

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int n = nums.size();
        for(auto x : nums){
            if(x < 0 || x >= n)
                return -1;
        }
        for(int i=0;i<n;i++){
            while(i != nums[i] && nums[nums[i]] != nums[i])   //重复元素交换操作直到无法交换为止
                swap(nums[i],nums[nums[i]]);
            if(i != nums[i] && nums[nums[i]] == nums[i])   //若第i个数未放到正确的位置上→查看是否出现重复元素
                return nums[i];
        }
        return -1;
    }
};