[leetcode daily question] - 268. Missing numbers

One 【 Topic category 】

• Array

Two 【 questions 】

• Simple

3、 ... and 【 Title number 】

• 268. Missing numbers

Four 【 Title Description 】

• Given an inclusion [0, n] in n Array of Numbers nums , find [0, n] The number that doesn't appear in the array in this range .

5、 ... and 【 Title Example 】

• Example 1：
  Input ：nums = [3,0,1]
  Output ：2
  explain ：n = 3, Because there is 3 A digital , So all the numbers are in range [0,3] Inside .2 It's the missing number , Because it didn't show up in nums in .

• Example 2：
  Input ：nums = [0,1]
  Output ：2
  explain ：n = 2, Because there is 2 A digital , So all the numbers are in range [0,2] Inside .2 It's the missing number , Because it didn't show up in nums in .

• Example 3：
  Input ：nums = [9,6,4,2,3,5,7,0,1]
  Output ：8
  explain ：n = 9, Because there is 9 A digital , So all the numbers are in range [0,9] Inside .8 It's the missing number , Because it didn't show up in nums in .

• Example 4：
  Input ：nums = [0]
  Output ：1
  explain ：n = 1, Because there is 1 A digital , So all the numbers are in range [0,1] Inside .1 It's the missing number , Because it didn't show up in nums in .

6、 ... and 【 Topic tips 】

• n == nums.length
• $1<=n<=10^4$
• 0 <= nums[i] <= n
• nums All the numbers in are unique

7、 ... and 【 Advanced title 】

• Can you achieve linear time complexity 、 The algorithm only uses extra constant space to solve this problem ?

8、 ... and 【 Their thinking 】

• This kind of topic is easy to think of Hash The idea of the table , Because the title says that all the numbers are unique , It also tells that the maximum value will not exceed the length of the array
• So let's first create an array map, Initialize to 0
• Then scan the incoming array , A certain number has appeared , will map The value of the corresponding position is set to 1, Indicates that there has been
• Finally scan 0~n, If map The corresponding position is 1, It means that , No operation ; If map The corresponding position is 0, Description does not appear , Just return this value
• In this way, the advanced requirements of the topic are achieved ： Linear time complexity 、 An algorithm that uses only the extra constant space

Nine 【 Time frequency 】

• Time complexity ：$O(N)$, among $N$ Is array length
• Spatial complexity ：$O(N)$, among $N$ Is array length

Ten 【 Code implementation 】

1. Java Language version

package Array;

public class p268_MissingNumbers {
    

    public static void main(String[] args) {
    
        int[] nums = {
    3, 0, 1};
        int res = missingNumber(nums);
        System.out.println("res = " + res);
    }

    public static int missingNumber(int[] nums) {
    
        int[] map = new int[nums.length + 1];
        for (int i = 0; i < nums.length + 1; i++) {
    
            map[i] = 0;
        }
        for (int i = 0; i < nums.length; i++) {
    
            map[nums[i]] = 1;
        }
        for (int i = 0; i < nums.length + 1; i++) {
    
            if (map[i] == 0) {
    
                return i;
            }
        }
        return 0;
    }

}

2. C Language version

#include<stdio.h>
#include<stdlib.h>

int missingNumber(int* nums, int numsSize)
{
    
	int* map = (int*)calloc(numsSize + 1, sizeof(int));
	for (int i = 0; i < numsSize; i++)
	{
    
		map[nums[i]] = 1;
	}
	for (int i = 0; i <= numsSize; i++)
	{
    
		if (map[i] == 0)
		{
    
			return i;
		}
	}
	return NULL;
}

/* The main function is omitted */

11、 ... and 【 Submit results 】

1. Java Language version
   

2. C Language version