13. 找出数组中重复的数字

思路：把每个数放到对应的位置上，即让 nums[i] = i

数组中第i个数nums[i]的正确位置是nums[nums[i]]

详见题解

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (nums[i] < 0 || nums[i] >= n) {
                return -1;
            }
        }
        for (int i = 0; i < n; i++) {
            while (nums[i] != nums[nums[i]]) {
                swap(nums[i], nums[nums[i]]);
            }
            if (nums[i] != i) {
                return nums[i];
            }
        }
        return -1;
    }
};

14. 不修改数组找出重复的数字

抽屉原理：n+1 个苹果放在 n 个抽屉里，那么至少有一个抽屉中会放两个苹果。
将区间[1, n]划分成[1, n/2]和[n/2+1, n]两个子区间，然后分别统计两个区间中数的个数

详见题解

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int l = 1, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1; // [l..mid] [mid+1..r]
            int s = 0; // 统计数的个数
            for (auto x : nums) {
                if (l <= x && x <= mid) {
                    s++;
                }
            }
            if (s > mid - l + 1) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};

2951. 不重复数字

利用 unordered_map

#include <iostream>
#include <unordered_map>
using namespace std;
int T, n, x;

int main() {
    scanf("%d", &T);
    while (T--) {
        unordered_map<int, bool> mp;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d", &x);
            if (mp[x] == false) {
                printf("%d ", x);
            }
            mp[x] = true;
        }
        puts("");
    }
    return 0;
}

73. 数组中只出现一次的两个数字

位运算

class Solution {
public:
    vector<int> findNumsAppearOnce(vector<int>& nums) {
        int sum = 0;
        for (auto x : nums) {
            sum ^= x;
        }
        int k = 0;
        while ((sum >> k & 1) == 0) {
            k++;
        }
        int first = 0;
        for (auto x: nums) {
            if (x >> k & 1) {
                first ^= x;
            }
        }
        return vector<int> {first, sum ^ first};
    }
};