class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        if (nums.empty())
            return -1;
        int n = nums.size();
        bool st[n] = {false};
        for (auto val:nums) {
            if (val < 0 || val >= n)
                return -1;
        }
        for (auto val:nums) {
            if (!st[val])
                st[val] = true;
            else 
                return val;
        }
        return -1;
    }
};




class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        if (nums.empty())
            return -1;
        int n = nums.size();
        for (auto val:nums){
            if (val < 0 || val >= n)
                return -1;
        }
        for (int i = 0; i < n; i++) { //让每个数字与下标对齐
            while (nums[nums[i]] != nums[i]) swap(nums[i], nums[nums[i]]);
            if (nums[i] != i) return nums[i];
        }


        return -1;
    }
};