j
jaryue
V1
2023/03/20阅读:18主题:默认主题
leecode268丢失的数字
leecode 268
题目描述
给定一个包含 [0, n] 中 n 个数的数组 nums ,找出 [0, n] 这个范围内没有出现在数组中的那个数。
解题思路
法1
排序法\
-
排序数组
sort.Ints(nums)//go语言内置函数,效果比自己写的更好
-
判断首位是否为0.题目描述是0-n,所以没0则返回0
if nums[0]!=0 {///判断首位是否为0
return 0
}
-
循环遍历查找缺少的数字
for i := 1; i < len(nums); i++ {//循环遍历查找缺少的数字
if nums[i] != nums[i-1]+1 {//若两数不相邻则有数字缺少
return nums[i] - 1
}
}
return nums[len(nums)-1] + 1//若无数字缺少,则返回最后一个数字加1
法2
哈希表
-
建立map -
赋值
for _, v := range nums { //循环赋值,给map中的出现过元素赋值
m[v] = true
}
-
查找缺少的数
for i := 0; ; i++ {//从0开始查找缺少的数
if !m[i] {
return i
}
}
法3
位运算异或 数组长度为n,又缺少一个数字,那么就是从0-n缺少一个数字,用数组里的所有元素与0-n进行异或操作,却少的数字只出现一次,结果就是那个数字.
-
循环异或数组中的值和1-n
for i := len(nums); i > 0; i-- {//循环异或每一个值,缺少一个0
j = j ^ i ^ nums[i-1]
}
-
返回异或结果
return j ^ 0//返回结果
执行结果
法1
func missingNumber(nums []int) int {
sort.Ints(nums)//go语言内置函数,效果比自己写的更好
if nums[0]!=0 {//判断首位是否为0
return 0
}
for i := 1; i < len(nums); i++ {//循环遍历查找缺少的数字
if nums[i] != nums[i-1]+1 {//若两数不相邻则有数字缺少
return nums[i] - 1
}
}
return nums[len(nums)-1] + 1//若无数字缺少,则返回最后一个数字加1
}
执行用时: 24 ms , 在所有 Go 提交中击败了 23.03% 的用户 内存消耗: 6.2 MB , 在所有 Go 提交中击败了 53.17% 的用户 通过测试用例: 122 / 122
法2
func missingNumber(nums []int) int {
m := make(map[int]bool) //建立map用于储存数值与状态
for _, v := range nums { //循环赋值
m[v] = true
}
for i := 0; ; i++ {//从0开始查找缺少的数
if !m[i] {
return i
}
}
}
执行用时: 20 ms , 在所有 Go 提交中击败了 35.89% 的用户 内存消耗: 6.5 MB , 在所有 Go 提交中击败了 7.87% 的用户 通过测试用例: 122 / 122
法3
// 位运算
func missingNumber(nums []int) int {
j := 0//储存运算结果数据
for i := len(nums); i > 0; i-- {//循环异或每一个值,缺少一个0
j = j ^ i ^ nums[i-1]
}
return j ^ 0//返回结果
}
执行用时: 16 ms , 在所有 Go 提交中击败了 65.83% 的用户 内存消耗: 6.2 MB , 在所有 Go 提交中击败了 53.17% 的用户 通过测试用例: 122 / 122
作者介绍
j
jaryue
V1