Make writing a habit together! This is the second day of my participation in the “Gold Digging Day New Plan · April More text challenge”. Click here for more details.

Offer 53-II. 0 ~ n-1

Offer 53-II. 0 ~ N-1, Offer 53-II. 0 ~ N-1

I. Title Description:

Back to Guangzhou from Shenzhen, now there is no free ride to the epidemic, where did my four stolen hours go

But I will still keep a good habit of learning and recording, after all, it is not easy to develop a good habit, just like physical exercise

Today is a simple question, the topic will be relatively clear, maybe we will think of the solution at the first time, but we have to understand that it will not be so simple

2. What ideas does this question examine? What’s your thinking?

We still need to walk through the process of doing the problem, which is a must and can not be skipped, because only we have considered and designed as much as possible in thinking, then the deviation in implementation can be as small as possible

Let’s see what this tells us:

  • The array given is an ordered array that must start at 0 and the maximum value is 10000
  • The problem is very clear. We need to find the missing element in the ordered array. According to the meaning given by the question, there will only be 1 element, not multiple elements
  • And finally we need to print out what the missing number is

Again, once we know what the important information is, we’re going to simulate it so that we can see the whole idea very clearly

First of all, we can certainly find the missing elements by using the way of foolproof ab initio traversal. There is no problem, but the time complexity will be relatively high, the highest time can reach 10000 times

Let’s choose to deduce another way, which is also easier to understand

We can do it in this dichotomous way, instead of going through it like we did at the beginning

As in the example above: 0-9, the number 5 is missing, so we use binary search

  • Validates the current left and right bounds and calculates the value of the current intermediate index
  • Verify that the current intermediate index corresponds to the value that should be present at the current position; for example, nums[5] should be present at 5 instead of 6
  • If the value that corresponds to the current intermediate index is less than it should be, then you need to look left, the left value is missing, and vice versa
  • And finally, when the left boundary is equal to the right boundary or the left boundary exceeds the right boundary, the value we’re looking for is the value of the left boundary

Once you have the idea, the next step is to implement it according to the idea

Three, coding

The control needs to be calculated logically when the left edge is smaller than the right edge

The encoding is as follows:

func missingNumber(nums []int) int {
     // In this case, we start at 0 by default. We initialize the left edge
    left := 0
    // Initialize the right edge to the length of the array
    right := len(nums)
    // Initializes an arbitrary intermediate node
    mid := 0
    for left < right {
        // Calculate the middle position
        mid = (left + right) /2
        // We know that nums is ordered. If the middle value is not the same as the middle value, then the left value is missing
        ifnums[mid] ! = mid { right = mid }else{
            // Otherwise, the right value is missing
            left = mid + 1}}return left
}
Copy the code

Based on the above code, it should be very clear, mainly to determine whether the specific missing number should be on the left or the right

Iv. Summary:

The time complexity of this problem is O(logn), and the space complexity is O(1), because we introduced a constant maturity level of space consumption

Offer 53-II. 0 ~ n-1

Today is here, learning, if there is a deviation, please correct

Welcome to like, follow and favorites

Friends, your support and encouragement, I insist on sharing, improve the quality of the power

All right, that’s it for this time

Technology is open, our mentality, should be more open. Embrace change, live in the sun, and strive to move forward.

I am Nezha, welcome to like, see you next time ~