找到所有数组中消失的数字

找到所有数组中消失的数字

题目描述

给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。

找到所有在 [1, n] 范围之间没有出现在数组中的数字。

您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

示例 1:

输入:
[4,3,2,7,8,2,3,1]
输出:
[5,6]

解法

方法1、若按序不重复存放，则 n 个元素刚好存放于大小为 n 的数组中，即每个下标 i 处存放元素值为 i+1。
根据题目中描述，数组中可能存在重复元素，且并未按序存放。所以不妨遍历数组，将每个元素调整到对应下标的位置，即将元素 k 存储于下标为 k-1 处。然后遍历数组，元素值与下标不匹配的即为消失元素数字。
方法2、先排序，再根据排序结果找出缺失的数字

package main

import "fmt"

func parse(a []int, begin int, end int) int {
    index := a[begin]
    for begin < end {
        for begin < end && a[end] >= index {
            end--
        }
        a[begin] = a[end]

        for begin < end && a[begin] <= index {
            begin++
        }
        a[end] = a[begin]
    }
    a[begin] = index

    return begin
}

func quick_sort(a []int, begin int, end int) {
    if begin < end {
        flag := parse(a, begin, end)
        quick_sort(a, begin, flag-1)
        quick_sort(a, flag+1, end)
    }
}

func FindMissingNum2(num []int) (result []int){
    quick_sort(num, 0, len(num)-1)
    fmt.Println(num)
    compare := 1
    for j := 0; j < len(num); j++ {
        if num[j] > compare {
            for k := compare; k < num[j]; k++ {
                result = append(result, k)
            }
            compare = num[j] + 1
        } else if num[j] == compare {
            compare++
        }
    }
    if compare <= len(num) {
        for i := compare; i <= len(num); i++ {
            result = append(result, i)
        }
    }
    fmt.Println(result)
    return result
}

func FindMissingNum1(num []int) (result []int){
    for i := 0; i < len(num); i++ {
        c := num[i]
        for num[c-1] != c {
            temp := num[c-1]
            num[c-1] = c
            c = temp
        }
    }
    fmt.Println(num)
    for j := 0; j < len(num); j++ {
        if num[j] != j +1 {
            result = append(result, j+1)
        }
    }
    fmt.Println(result)
    return result
}

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

    num = []int{4,3,2,7,8,2,2,3,1,1,4}
    fmt.Println(FindMissingNum2(num))
}

运行结果：

GOPATH=F:\goPath #gosetup
C:\Go\bin\go.exe build -o C:\Users\windows10\AppData\Local\Temp\___go_build_FindMissingNum_go.exe F:/code/test/FindMissingNum/FindMissingNum.go #gosetup
C:\Users\windows10\AppData\Local\Temp\___go_build_FindMissingNum_go.exe #gosetup
[1 2 3 4 8 2 7 8 1 1 4]
[5 6 9 10 11]
[5 6 9 10 11]
[1 1 2 2 2 3 3 4 4 7 8]
[5 6 9 10 11]
[5 6 9 10 11]

Process finished with exit code 0