This is the 15th day of my participation in the August More Text Challenge. For details, see:August is more challenging

Topic Description:

268. Missing Numbers – LeetCode (leetcode-cn.com)

Given an array nums containing n numbers in [0, n], find the number in the range [0, n] that does not appear in the array.

Advanced:

  • Can you solve this problem with a linear time complexity algorithm using only extra constant space?

Example 1:

Input: nums = [3,0,1] output: 2 description: n = 3, because there are three digits, so all digits are in the range [0,3]. 2 is the missing number because it does not appear in nums.Copy the code

Example 2:

Input: nums = [0,1] output: 2 description: n = 2, because there are two digits, so all digits are in the range [0,2]. 2 is the missing number because it does not appear in nums.Copy the code

Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1] output: 8 description: n = 9, because there are nine digits, so all digits are in the range [0,9]. 8 is the missing number because it does not appear in nums.Copy the code

Example 4:

Input: nums = [0] Output: 1 Description: n = 1, because there is one digit, so all digits are in the range of [0,1]. 1 is the missing number because it does not appear in nums.Copy the code

Tip:

  • n == nums.length
  • $1 <= n <= 10^4$
  • 0 <= nums[i] <= n
  • numsAll of the numbers inunique

Thought analysis

The sorting

When an array is ordered, two neighboring numbers must be one off each other, so it’s easy to figure out which number is missing after sorting the array.

The thing to notice here is that when you’re dealing with the bounding case, the missing digit is the first digit, you can handle that inside the for loop, and if you’re missing the last digit, you can handle that outside of the loop, which is the last return, which is the return that’s not happening in the for loop.

AC code

class Solution {
    fun missingNumber(nums: IntArray): Int {
        nums.sort()
        for ((index, value) in nums.withIndex()) {
            if(index ! = value)return index
        }
        return nums.size
    }
}

Copy the code

Mathematics method

We can use the Gaussian summation formula to sum [0..n] and subtract the sum of all the numbers in the array to get the missing number. The Gauss summation formula is


∑ i = 0 n i = n ( n + 1 ) 2 \sum_{i=0}^{n}i = \frac{n(n+1)}{2}

AC code

class Solution {
    fun missingNumber(nums: IntArray): Int {
        var sum = (1 + nums.size) * nums.size / 2
        for(i in nums){
            sum -= i
        }
        return sum
    }
}

Copy the code

conclusion

This question is relatively simple, but there is a risk of overflow in the mathematical method, which may not be in the test case, so it passed

In fact, before leetcode.136 only appears once in the number (juejin. Cn) we have used xOR solution problem, this problem can also use this method, can prevent overflow.

reference

Missing Numbers-Missing numbers-Force button (LeetCode) (leetcode-cn.com)