algo-aha

[1..n]间的数，有的出现2次、有的1次、有的缺失，找重复的那些数（in-place算法）

• https://leetcode.com/problems/find-all-duplicates-in-an-array

vector<int> findDuplicates(vector<int>& nums) {
    // 把数x当作下标（1-based），将nums[x-1]标记为负数
    vector<int> ans;
    for (int num : nums) {
        int x = abs(num);
        if (nums[x-1] < 0) ans.push_back(x);
        else nums[x-1] *= -1;
    }
    return ans;
}

[1..n]间的数，有一个数重复、一个数缺失，找这两个数

• https://leetcode.com/problems/set-mismatch/

同上的in-place算法

vector<int> findErrorNums(vector<int>& nums) {
    const int N = nums.size();
    int dup = -1, missing = -1;
    // 把数x当作下标（1-based），将nums[x-1]标记为负数
    for (int num : nums) {
        int x = abs(num);
        if (nums[x-1] < 0) {
            dup = x;
        } else {
            nums[x-1] *= -1;
        }
    }
    // 哪个下标位置仍是正数
    for (int i = 0; i < N; i++) {
        if (nums[i] > 0) missing = i + 1;
    }
    return {dup, missing};
}

或者用位操作

vector<int> findErrorNums(vector<int>& nums) {
    const int N = nums.size();
    int x = 0;
    for (int num : nums) x ^= num;
    for (int i = 1; i <= N; i++) x ^= i;
    // x = duplicate^missing
    int lastBit = x & -x;
    int xor0 = 0, xor1 = 0;
    for (int num : nums) {
        if (num & lastBit) xor1 ^= num;
        else xor0 ^= num;
    }
    for (int i = 1; i <= N; i++) {
        if (i & lastBit) xor1 ^= i;
        else xor0 ^= i;            
    } 
    // xor0和xor1 是 duplicate和missing，不知哪个是哪个
    for (int num : nums) {
        if (num == xor0) {
            return { xor0, xor1 };
        }
    }
    return { xor1, xor0 };
}

长为n的数组中放[1..n]间的数，有的出现多次、有的缺失，in-place统计各出现的次数

vector<int> statArray(vector<int> &nums) {
    // 把数x当作下标（1-based），在下标处计数nums[x-1]++，计数最多增N；
    // 为不影响nums[x-1]原先的值，先将所有数*=(N+1)，
    // 这时数x的下标处计数为nums[x/(N+1)-1]++。
    const int N = nums.size();
    for (int &x : nums) {
        x *= (N + 1);
    }
    for (int x : nums) {
        nums[x / (N + 1) - 1]++;
    }

    vector<int> ans;
    for (int x : nums) {
        // x/(N+1) => nums[x/(N+1)-1]%(N+1)
        ans.push_back(nums[x / (N + 1) - 1] % (N + 1));
    }
    return ans;
}

长为n+1的数组中放[1,n]间的数，至少有个数重复，找任一重复的数

• https://leetcode.com/problems/find-the-duplicate-number

不修改数组的 快慢指针法

是否有m长子段连续重复k次

• https://leetcode.com/problems/detect-pattern-of-length-m-repeated-k-or-more-times/

bool containsPattern(vector<int>& arr, int m, int k) {
    // 是否有m长子段连续重复k次
    const int N = arr.size();
    int count = 0;
    for (int i = 0; i + m < N; i++) {
        if (arr[i] != arr[i+m]) {
            count = 0;
        } else {
            count++;
            if (count == m * (k-1)) return true;
        }
    }
    return false;
}