Detailed explanation of the example of missing numbers in Go language problem LeetCode268

Question description

Original topic link:

268. Lost numbers

Given a contains[0, n]middlenArray of numbersnums, find out[0, n]The number that does not appear in the array within this range.

Example 1:

enter：nums = [3,0,1]
Output：2
explain：n = 3，Because there is 3 Numbers，So all numbers are in range [0,3] Inside。2 It's the missing number，Because it didn't appear in nums middle。

Example 2:

enter：nums = [0,1]
Output：2
explain：n = 2，Because there is 2 Numbers，So all numbers are in range [0,2] Inside。2 It's the missing number，Because it didn't appear in nums middle。

Example 3:

enter：nums = [9,6,4,2,3,5,7,0,1]
Output：8
explain：n = 9，Because there is 9 Numbers，So all numbers are in range [0,9] Inside。8 It's the missing number，Because it didn't appear in nums middle。

Example 4:

enter：nums = [0]
Output：1
explain：n = 1，Because there is 1 Numbers，So all numbers are in range [0,1] Inside。1 It's the missing number，Because it didn't appear in nums middle。

hint:

n ==

1 <= n <= 10^4

0 <= nums[i] <= n

All numbers in nums are unique

Advanced: Can you solve this problem by implementing linear time complexity and using only additional constant space algorithms?

Idea Analysis

After getting this question, I found that it gives n numbers in the range [0,n], that is, this is a highly adaptable idea of ​​sorting the array. For a complete array, it should be sorted as an array collection that is exactly the same as the subscript value. Then the solution is very simple. Find the first subscript that does not match the element, which is the missing number;

AC Code

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        ()
        for i in range(len(nums)):
            if nums[i] != i:
                return i
        return len(nums)

XOR twice - missing number

Problem-solving ideas

XOR is an interchangeable operation. The same number is equal to zero.

So we first find the range of the data and directly find the largest number. It should be noted here that if the largest number is less than the length of the array, the missing number is the largest number +1.

Then we accumulate all numbers of [0, n] and then all elements in the array are XORed, and in the end we are only the only number that does not appear. Because the other numbers appear twice.

Code

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = 0;
        int ans = 0;
        for (auto num: nums) {
            n = max(n, num);
            ans ^= num;
        }
        if (() > n) n = ();
        for (int i = 0; i <= n; i++) {
            ans ^= i;
        }
        return ans;
    }
};

C++ sort binary, addition and subtraction, XOR - missing numbers

Problem solution:

The first idea when I saw this question is dichotomy. First, sort the numbers, and then judge whether it is on the left or on the right through the mid value. nums[mid] == mid description is on the right, otherwise it is on the left, but in the end, you should also pay attention to the situation where the last number is missing. Then we must judge based on the last number and then return. The code is as follows:

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        sort((), ());
        int left = 0, right = () - 1;
        while(left < right) {
            int mid = (left + right) / 2;
            if(nums[mid] == mid) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return (right == () - 1 && nums[right] == right) ? right + 1 : right;
    }
};

But obviously there is no need to be that complicated and inefficient. The most global idea is to add all subscripts and subtract all the arrays. The rest are the missing numbers, the code is as follows:

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int total = 0;
        int i;
        for(i = 0; i < (); i ++) {
            total += i;
            total -= nums[i];
        }
        total += i;
        return total;
    }
};

The XOR method is actually the same as the addition and subtraction method, but the underlying principles are different. The ideas are all offsetting the same, leaving the only one with the code as follows:

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int total = 0;
        int i;
        for(i = 0; i < (); i ++) {
            total ^= i;
            total ^= nums[i];
        }
        total ^= i;
        return total;
    }
};

The above is the detailed explanation of the detailed explanation of the missing number example of Go language problem LeetCode268. For more information about the missing number example of Go problem solution, please pay attention to my other related articles!