leecode268丢失的数字

leecode 268

题目描述

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

解题思路

法1

排序法\

1. 排序数组

sort.Ints(nums)//go语言内置函数,效果比自己写的更好

2. 判断首位是否为0.题目描述是0-n,所以没0则返回0

if nums[0]!=0 {///判断首位是否为0
  return 0
 }

3. 循环遍历查找缺少的数字

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

哈希表

1. 建立map
2. 赋值

for _, v := range nums { //循环赋值,给map中的出现过元素赋值
  m[v] = true
 }

3. 查找缺少的数

for i := 0; ; i++ {//从0开始查找缺少的数
  if !m[i] {
   return i
  }
 }

法3

位运算异或 数组长度为n,又缺少一个数字,那么就是从0-n缺少一个数字,用数组里的所有元素与0-n进行异或操作,却少的数字只出现一次,结果就是那个数字.

1. 循环异或数组中的值和1-n

for i := len(nums); i > 0; i-- {//循环异或每一个值,缺少一个0
  j = j ^ i ^ nums[i-1]
 }

2. 返回异或结果

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