题解 | #数组中重复的数字#

// 法一：最笨方法，用set记录遍历过的数字
class Solution1 {
public:
    int duplicate(vector<int>& numbers) {
        unordered_set<int> seen;
        for (int x: numbers) {
            if (seen.count(x)) {
                return x;
            }
            seen.emplace(x);
        }
        return -1;
    }
};

// 法二：因为数字在0~n-1之间，可以让数字在下标的位置上
class Solution {
public:
    int duplicate(vector<int>& number) {
        for (int i = 0; i < number.size(); ++i) {
            while (number[i] != i) {
                if (number[i] == number[number[i]]) {
                    return number[i];
                }
                int tmp = number[number[i]];
                number[number[i]] = number[i];
                number[i] = tmp;
            }
        }
        return -1;
    }
};