LeetCode Notes: Numbers Missing From 0 to N-1

#leetcode

Question

All numbers in an increasing sorted array of length n-1 are unique, and each number is in the range of 0 to n-1. There is only one number among n numbers in the range 0～n-1 that is not in the array. Please find this number.

Example 1:

Enter: [0,1,3]

Output: 2

Example 2:

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

Output: 8

limit:

1 <= array length <= 10000

Solution

Analysis:

  1. Try to use reduce to solve, run the following program
[0,1,2,3,5,6].reduce((a,b)=>{
    console.info(a,b)
    return a + 1
})

// output
0 1 // Difference by 1
1 2 // Difference by 1
2 3 // Difference by 1
3 5 // Difference 2
4 6 // Difference 2

We find that when the difference between b and a is 2 for the first time, it is the position of the default number we are looking for, which is a+1, where the result is 4

  1. After testing, it is found that there are two special cases, namely the default numbers at the beginning and the end. Run the following program

Default 6

[0,1,2,3,4,5].reduce((a,b)=>{
    console.info(a,b)
    return a + 1
})

// output
0 1
1 2
2 3
3 4
4 5

as well as Default 0

[1,2,3,4,5].reduce((a,b)=>{
    console.info(a,b)
    return a + 1
})

// output
1 2
2 3
3 4
4 5

We found that none of them have a difference of 2 between b and a. Two steps:

  • Directly determine whether the beginning of the array is 0, if it is not 0, directly return to the default value of 0
  • The next step is to traverse the array to find if there is a b-a = 2 situation, if not, you can determine that the default number is at the end of the array

Code:

/**
  * @param {number[]} nums
  * @return {number}
  */
var missingNumber = function(nums) {

     // Special treatment 0 does not exist
     if(nums[0] !== 0) return 0
    
     let result = 0
     nums.reduce((a,b)=>{
         // The first time the difference is 2, the number between a and b is the default number
         if(b-a === 2 && result === 0){
             result = a + 1
         }
         return a + 1
     })
     // result is always equal to 0, indicating that there is no difference between b and a by 2, it can be determined that the default is the last number, and the length of the array is the result value
     return result === 0? nums.length: result
};

Reference

Comments