2021-12-19: find the missing numbers in all arrays. Give you an n

2021-12-19： Find all the missing numbers in the array .

Here's one for you n Array of integers nums , among numsi In the interval 1, n Inside . Please find out all in 1, n Range but not in nums Number in , And return the result in the form of array .

Advanced ： You can use no extra space and the time complexity is O(n) Solve this problem in the case of ? You can assume that the returned array is not included in the extra space .

Power button 448.

answer 2021-12-19：

Subscript loop . strive for i Place i+1.

Time complexity ：O(N).

Extra space complexity ：O(1).

The code to use golang To write . The code is as follows ：

package main

import "fmt"

func main() {
    nums := []int{4, 3, 2, 7, 8, 2, 3, 1}
    ret := findDisappearedNumbers(nums)
    fmt.Println(ret)
}

func findDisappearedNumbers(nums []int) []int {
    ans := make([]int, 0)
    if len(nums) == 0 {
        return ans
    }
    N := len(nums)
    for i := 0; i < N; i++ {
        //  from i Set out , Play subscript loop 
        walk(nums, i)
    }
    for i := 0; i < N; i++ {
        if nums[i] != i+1 {
            ans = append(ans, i+1)
        }
    }
    return ans
}

func walk(nums []int, i int) {
    for nums[i] != i+1 { //  Constantly from i deliver goods 
        nexti := nums[i] - 1
        if nums[nexti] == nexti+1 {
            break
        }
        nums[i], nums[nexti] = nums[nexti], nums[i]
    }
}

The results are as follows ：

picture

Zuo Shen java Code