找到所有数组中消失的数字
题目描述
给定一个范围在 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