//001:找出数组中的重复数字
class Solution {
public:
    //直接把数组中的数字加到multi里面
    int duplicateInArray(vector<int>& nums) {
        multiset<int>buff;
        for (auto n:nums) {
            if (n < 0 || n > nums.size())
                return -1;
            buff.insert(n);
        }

        multiset<int>::iterator begin = buff.begin();
        for (;begin != buff.end(); ++begin) {
            if (buff.count(*begin) > 1)
                return *begin;
        }
        return -1;
    }
};

class Solution {
public:
    //原地算法，空间复杂度为O(1)
    int duplicateInArray(vector<int>& nums) {
        int n = nums.size();

        for (auto i:nums) {
            if (i < 0 || i > n)
                return -1;
        }
        for (int i = 0; i < n; ++i) {
            while (nums[i] != i && nums[nums[i]] != nums[i])
                swap(nums[i], nums[nums[i]]);
            if (nums[i] != i)
                return nums[i];
        }
        return -1;
    }
};