Practice deliberately and improve daily.

Topic:

Analysis:Find numbers that do not appear in range N: either N or within N, and understand the difference:<Is less than N, so let it be:

  1. N, the number conforming to the characteristic;
  2. N+1

The most straightforward code that is likely to be easy to write:

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        star = max(nums)
        for i in range(star):
            if i not in nums:
                star = i
                return star
        return star+1
Copy the code

It did pass after submission, but you can see that it’s not very efficient and we need to see further

Turn over a solution, the official solution is more representative, proposed: “sorting”, “hash”, “mathematics”, “bit operation” four ways, mathematics is not so representative (not all algorithm questions have the corresponding mathematical formula directly solved, can first go over, the other three in turn to understand.

  • Mathematical method:

Use the summation formula, also known as Gauss’s formula, to calculate the addition within N, where the missing number is the difference between the sum and the sum, for example:

Take example 4 from the problem:

If N = 9, total=45, total= 37, star =total-sum(nums)=8

So the code should look like this:

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        total = n*(n+1)//2
        gaosi_sum = sum(nums)
        return total - gaosi_sum
Copy the code

I started with a little bit of judgment, if it’s zero or something like that, and I check it and I just return the difference. Alternatively, we can change the built-in function sum to subtract the median nums value by total and return total.