Array subscript is still very useful ~ violent solution optimization to classical binary search, as the basic algorithm of the entry is good ~

🌟 (refer to LeeCode easy 🌟, medium 🌟 🌟, difficult 🌟 🌟)

In addition, algorithm questions usually examine and analyze time complexity and space complexity, which can be referred to the author’s previous article

“Data Structures & Algorithms” series: 3. Time & Space Complexity (2)

The missing number from 0 to N-1

Topic describes

Reference to missing numbers in Offer 53-II. 0 to n-1

All numbers in an incrementally sorted array of length n-1 are unique, and each number is in the range 0 to n-1. Find one and only one of the n digits in the range 0 to n-1 that is not in the array.

Example 1:

Input:,1,3 [0]

Output: 2

Example 2:

Input:,1,2,3,4,5,6,7,9 [0]

Output: 8

Limitations:

1 <= Array length <= 10000

Their thinking

Methods a

It is not difficult to imagine that the subscript and the value are ==

The following is an example of Go:

func missingNumber(nums []int) int {
    for i, v := range nums {
        ifi ! = v {return i
        }
    }
    return len(nums)
}
Copy the code

Complexity? 🙌 O (n)

Method 2

Continue to optimize, sort array lookup optimization is not difficult to think of using dichotomy, the idea is as follows:

func missingNumber(nums []int) int {
    left := 0
    right := len(nums)
    for left < right {
        mid := (left + right) >> 1 // Divide by 2
        ifnums[mid] ! = mid {//nums is an ordered array. If mid and number are different, search on the left
            right = mid
        } else { // Mid is the same as number, missing number is in the right, left rounded up +1
            left = mid + 1}}return left
}
Copy the code

Complexity? 🙌 O (logn)

Methods three

The use of the sum difference, associated with the Olympic number problem ah-ha 🐂

  1. Calculates the sum count when the array is free of numbers
  2. Count minus the sum of the array nums
  3. The resulting difference is the missing number

Methods four

Record the number using an array in which the number has the same index as the array

  • Apply for a bool array flag whose length is Len (nums)+1
  • Iterate through the NUMS array and record the value of the index corresponding to the number in the Flag array as true
  • Iterate through the flag array again, and the index with a value of false is the missing number

conclusion

I did not think there are methods three, four, all rely on the wisdom of netizens [Golang] dichosis, or, difference, mark, show ah ~

I do not understand the xor method mentioned in ↑ 😂

The question itself is not difficult, the interview method 2, remember to show the sum difference of method 3 ~

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign