268. Missing numbers

Given an array num containing N numbers in [0, n], find the number that does not appear in the array within the range of [0, n].

Example 1:

Input: nums = [3,0,1]
Output: 2
 Explanation: n = 3，Because there are three numbers, all the numbers are in the range [0,3] Inside. 2 is the missing number because it does not appear in nums Yes.
Example 2:

Input: nums = [0,1]
Output: 2
 Explanation: n = 2，Because there are two numbers, all the numbers are in the range [0,2] Inside. 2 is the missing number because it does not appear in nums Yes.

Hash solution

This should be the simplest solution. Record each element of the array with a hash table, and then judge whether 0 ~ n is in the hash table one by one. If the element is not found in the hash table, it is the missing number.

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        unordered_set<int> set(nums.begin(), nums.end());
        for(int i = 0; i <= nums.size(); ++i)
            if(set.count(i) == 0)
                return i;
        return -1;
    }
};

• Time complexity: O(N)
• Space complexity: O(N)
  

sort

If the array is sorted in ascending order and no element is missing, the order must be 0 ~ n:

• Original array: 3 2 1 0 4
• After sorting: 0 1 2 3 4
  Obviously, there is a law of num [i] = = I.
  If there is any deficiency, it needs to be divided into two situations:
• If the missing element is in the [0, n - 1] interval, it must be obtained by checking the elements one by one (judge num [i] = = I).
• The missing elements are equal to N, that is, 0 ~ n - 1 (n in total) are in the array, then the elements in the array must be legal. In this case, you can directly return n as the missing number.

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        for(int i = 0; i < n; ++i){
            if(nums[i] != i)
                return i;
        }
        return n;
    }
};

• Time complexity: O(NlogN)
• Space complexity: O(1)
  

mathematics

You can first find the sum of 0 ~ n, and subtract the sum of the elements of the array num from sum to get the missing number.
According to the arithmetic sequence formula sum = n * (n + 1) / 2.

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int sum = n * (n + 1) / 2;
        for(int& num:nums)
            sum -= num;
        return sum;
    }
};

• Time complexity: O(N)
• Space complexity: O(1)
  

Bit operation

After adding 0 to n (n - 1 numbers in total) to the number of the original array, only the missing number in the array will appear once. For example, the element of the original array is [3, 0, 1], the missing number is 2, and after adding 0 ~ 3, it will become [3, 0, 1, 0, 1, 2, 3]. Except for the missing number 2, the other numbers will appear twice.
Therefore, these elements that appear twice can be eliminated by XOR operation, and finally the missing elements can be obtained.

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        //XOR the array with missing x, and then get the missing number through 0 ~ n XOR
        int x = 0;
        int n = nums.size();
        for(int& num:nums)
            x ^= num;
        for(int i = 0; i <= n; ++i)
            x ^= i;
        return x;
    }
};

• Time complexity: O(N)
• Space complexity: O(1)
  

In situ hash

The total number of elements is n + 1, and the array size is only n. therefore, you can add an element - 1 that is not in the array, so that the array size is n + 1,
Suppose the definition is reasonable: num [i] = = I, that is, the current number is equal to its array subscript.
Judge the element. If the current element is unreasonable and not equal to - 1, change the element to its reasonable position: swap (Num [i], Num [num [i]]; Make the judgment again.

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

• Time complexity: O(N)
• Space complexity: O(1)