面试题 17.19

You are given an array with all the numbers from 1 to N appearing exactly once, except for two number that is missing. How can you find the missing number in O(N) time and 0(1) space?

You can return the missing numbers in any order.

Example 1:

Input: [1] Output: [2,3] Example 2:

Input: [2,3] Output: [1,4] Note:

nums.length <= 30000

Solutions

1. operations

2. find n1 ^ n2, then partion n1 and n2 based on the rightmost 1 bit as the partition marker.

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        // n1 ^ n2
        int mix = 0, all = 0;
        int maxn = nums.size() + 2;
        for (int n = 1; n <= maxn; n++)
            mix ^= n;
        for (auto n : nums)
            mix ^= n;
        // the rightmost 1 bit
        int diff = mix & -mix;

        int n1 = 0;
        for (auto n : nums)
            if (n & diff)
                n1 ^= n;

        for (int n = 1; n <= maxn; n++)
            if (n & diff)
                n1 ^= n;

        return {n1, n1 ^ mix};
    }
};

1. math

2. pigeonhole

3. Put each number at it's appropriate position.

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int n = nums.size();

        nums.push_back(0);
        nums.push_back(0);
        for (int i = 0; i < n; i++) {
            while (nums[i] != 0 && nums[i] != i + 1)
                swap(nums[nums[i] - 1], nums[i]);
        }
        vector<int> res;
        for (int i = 0; i < n + 2; i++)
            if (i + 1 != nums[i])
                res.push_back(i + 1);

        return res;
    }
};