This is the sixth day of my participation in the November Gwen Challenge. See details: The Last Gwen Challenge 2021.

Topic describes

This is 268 on LeetCode. The missing number is easy.

Tag: “simulation”, “hash table”, “bit operation”, “math”

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

Example 1:

Input: nums = [3,0,1] output: 2 explanation: n = 3 because there are three numbers, so all the numbers 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, all the 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 explanation: n = 9 because there are nine digits, so all the 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 Explanation: n = 1, because there is one digit, so all the digits are in the range [0,1]. 1 is the missing number because it does not appear in NUMS.Copy the code

Tip:

  • n == nums.length

  • 1 < = n < = 1 0 4 1 <= n <= 10^4

  • 0 < = n u m s [ i ] < = n 0 <= nums[i] <= n
  • All numbers in NUMS are unique

Advancements: Can you solve this problem with linear time complexity using only an extra constant space algorithm?

Sorting system

Numsnumsnums [I]≠inums[I] \neq inums[I]= I If there is no location where nums[I]≠inums[I] \neq inums[I]= I, then NNN is the answer.

Code;

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        for (int i = 0; i < n; i++) {
            if(nums[i] ! = i)return i;
        }
        returnn; }}Copy the code
  • Time complexity: assumedArrays.sortA two-axis quickrow implementation is used. Complexity of
    O ( n log ⁡ n ) O(n\log{n})
  • Space complexity: O(log⁡n)O(\log{n})O(logn)

An array of the hash

[0,n][0,n][0,n] [0,n][0,n][0,n] [0,n][0,n][0,n]

Code:

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        boolean[] hash = new boolean[n + 1];
        for (int i = 0; i < n; i++) hash[nums[i]] = true;
        for (int i = 0; i < n; i++) {
            if(! hash[i])return i;
        }
        returnn; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

In situ hash

In fact, we can use numsnumsnums itself as a hash table, place nums[I]nums[I]nums[I]nums[I] at its proper location iii (I

Code:

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if(nums[i] ! = i && nums[i] < n) swap(nums, nums[i], i--); }for (int i = 0; i < n; i++) {
            if(nums[i] ! = i)return i;
        }
        return n;
    }
    void swap(int[] nums, int i, int j) {
        intc = nums[i]; nums[i] = nums[j]; nums[j] = c; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(1)O(1)O(1)

A differential method

Numsnumsnums = [1,n][1, n][1,n] [1,n] Then calculate the sum of numsnumsnums, curcurcur, and the difference between the two is the missing numsnumsnums.

Code:

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int cur = 0, sum = n * (n + 1) / 2;
        for (int i : nums) cur += i;
        returnsum - cur; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(1)O(1)O(1)

Exclusive or

Find missing number, find a number of occurrences are xOR classic applications.

We can obtain the xOR and Ansansans of [1,n][1, n][1,n], and then use Ansansans to perform xor for each nums[I]nums[I].

In this final xOR and expression, only the missing element appears 111 times, and the other elements appear twice (X ⊕x=0x ⊕x=0x ⊕x=0x ⊕x=0), that is, the final answer ansansans is the missing element.

Code:

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int ans = 0;
        for (int i = 0; i <= n; i++) ans ^= i;
        for (int i : nums) ans ^= i;
        returnans; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(1)O(1)O(1)

The last

This is No.268 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01, and there are 1916 topics in LeetCode by the start date.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.