LeetCode Notes: Missing Number

#leetcode

Question

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Example 1:

Input: nums = [3,0,1]

Output: 2

Explanation**:** n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2:

Input: nums = [0,1]

Output: 2

Explanation**:** n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3:

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

Output: 8

Explanation**:** n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

Example 4:

Input: nums = [0]

Output: 1

Explanation**:** n = 1 since there is 1 number, so all numbers are in the range [0,1]. 1 is the missing number in the range since it does not appear in nums.

Constraints:

  • n == nums.length
  • 1 <= n <= 104
  • 0 <= nums[i] <= n
  • All the numbers of nums are unique.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

Solution One

Analysis:

  1. Sort the numbers in the array first
  2. Traverse the array again to check whether the subscript and the value of the array can correspond, the uncorresponding number is the missing numebr
  3. Finally, consider the case where there is only 0 and the case where the missing number is the last one

Code:

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    const find = nums.sort((a,b) => a-b).findIndex((n,i) => {
        return n !== i 
    })
    return find !== -1 ? find : nums.length
};

Solution Two

Analysis:

Traverse the numbers of 0 - n and check if they exist in the nums array. The numbers not in the nums array is the missing number.

Code:

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    for(let i = 0; i < nums.length + 1; i++){
        if(!nums.includes(i)){
            return i
        }
    }
};

Solution Three

Analysis:

According to the above solution two, the performance of the includes method of directly using the array is not very good. We switch to the Set collection and use the has of the Set to find elements to improve query efficiency.

Code:

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    const set = new Set(nums)
    for(let i = 0; i < nums.length + 1; i++){
        if(!set.has(i)){
            return i
        }
    }
};

Reference

Comments