class Solution {
    public:
        int duplicateInArray(vector<int>& nums)
        {
            vector<int> arr(nums);//迭代器不管有没有添加元素，内存大小固定，类似指针变量
            int n=nums.size();
            for(int i=1;i<=n;i++)
            {
                while(arr[i-1]!=i && arr[i-1]!=arr[arr[i-1]])
                    swap(arr[i-1],arr[arr[i-1]]);
                if(arr[i-1]!=i)
                    return arr[i-1];
            }
        }
};