645. Set Mismatch

The set S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetition of one number and loss of another number.

Given an array nums representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array.

Example 1:

Input: nums = [1,2,2,4]
Output: [2,3]

Note:

1. The given array size will in the range [2, 10000].

2. The given array's numbers won't have any order.

暴力解先紀錄每個數字出現的次數，然後再掃描第二遍找到出現零次和出現兩次的數就是所求。

// Two pass naive method
vector<int> findErrorNums(vector<int>& nums) { // time: O(n); space: O(n)
    int n = nums.size();
    vector<int> record(n, 0), res(2, -1);
    for (int num : nums) ++record[num - 1];
    for (int i = 0; i < n; ++i) {
        if (record[i] == 2) res[0] = i + 1;
        else if (record[i] == 0) res[1] = i + 1;
    }
    return res;
}

一樣需要額外的空間紀錄每個數字出現的次數，然後用一個size為2的res數列紀錄結果，掃描的過程對res[1]跟(index + 1)和當前這個數做XOR，(index + 1)的意思是掃描完所有數之後res[1]會跟所有1~n之間的數做過一次XOR，但因為有數字出現兩次，有數字出現零次，所以res[1]掃描完時會呈現出現兩次和零次的數字的XOR。此外過程中如果發現出現兩次的數字，就用res[0]記錄下來。最後把res[1]和res[0]做XOR就可以得到出現零次的數存在res[1]。

// One pass with O(n) space
vector<int> findErrorNums(vector<int>& nums) { // time: O(n); space: O(n)
    int n = nums.size();
    vector<int> count(n, 0), res(2, 0);
    for (int i = 0; i < n; ++i) {
        res[1] ^= (i + 1) ^ nums[i];
        if (++count[nums[i] - 1] == 2) {
            res[0] = nums[i];
        }
    }
    res[1] ^= res[0];
    return res;
}

用一個size為2的res數列紀錄結果。掃描第一次時如果看到數字為正，那將它乘上一個負號，如果過程中看到負數，代表這個數已經出現第二次，先用res[0]把這個數記錄下來。掃描第二次時如果看到數字大於零，說明那個數出現零次，因為如果出現過的話第一次掃瞄就會把它變成負數了。

// Two pass with constant space
vector<int> findErrorNums(vector<int>& nums) { // time: O(n); space: O(1)
    vector<int> res(2, -1);
    for (int num : nums) {
        if (nums[abs(num) - 1] < 0) res[0] = abs(num);
        else nums[abs(num) - 1] *= -1;
    }
    for (int i = 0; i < nums.size(); ++i) {
        if (nums[i] > 0) res[1] = i + 1;
    }
    return res;
}

如果1到n的數字都存在在input裡的話，可以用num[i] - 1當作每個數字該存的位置，第一次掃瞄就是看到如果沒放在該放的位置的數就swap，第二次掃描時如果看到位置和數不符合的情況，就可以得到所求。

// Two pass with constant space
vector<int> findErrorNums(vector<int>& nums) { // time: O(n); space: O(1)
    int n = nums.size();
    // put the numbers to their correct positions
    for (int i = 0; i < n; ++i) {
        while (nums[i] != nums[nums[i] - 1]) swap(nums[i], nums[nums[i] - 1]);
    }
    for (int i = 0; i < n; ++i) {
        if (nums[i] != i + 1) return {nums[i], i + 1};
    }
    return {-1, -1};
}