题目
给定一个包含 [0, n] 中 n 个数的数组 nums，找出 [0, n] 这个范围内没有出现在数组中的那个数。
示例 1：
- 输入：
nums = [3,0,1]- 输出：
2- 解释：
n = 3，因为有3个数字，所以所有的数字都在范围[0,3]内。2是丢失的数字，因为它没有出现在nums中。
示例 2：
- 输入：
nums = [0,1]- 输出：
2- 解释：
n = 2，因为有2个数字，所以所有的数字都在范围[0,2]内。2是丢失的数字，因为它没有出现在nums中。
示例 3：
- 输入：
nums = [9,6,4,2,3,5,7,0,1]- 输出：
8- 解释：
n = 9，因为有9个数字，所以所有的数字都在范围[0,9]内。8是丢失的数字，因为它没有出现在nums中。
示例 4：
- 输入：
nums = [0]- 输出：
1- 解释：
n = 1，因为有1个数字，所以所有的数字都在范围[0,1]内。1是丢失的数字，因为它没有出现在nums中。
方法一：排序
思路及解法
将数组排序之后，即可根据数组中每个下标处的元素是否和下标相等，得到丢失的数字。
由于数组的长度是 ，因此下标范围是
。假设缺失的数字是
，分别考虑以下两种情况：
当
时，对任意
，都有
，由于
缺失，因此
，
当
时，
到
都没有缺失，因此对任意
，都有
根据上述两种情况，可以得到如下方法得到丢失的数字：
从左到右遍历数组
，如果存在
，则缺失的数字是满足
；
如果对任意
。
代码
class Solution {
func missingNumber(_ nums: [Int]) -> Int {
let tempNums: [Int] = nums.sorted()
for i in 0..<tempNums.count {
if tempNums[i] != i {
return i
}
}
return tempNums.count
}
}
复杂度分析
时间复杂度：
，其中
，遍历数组寻找丢失的数字的时间复杂度是
，因此总时间复杂度是
空间复杂度：
，其中
方法二：哈希集合
思路及解法
使用哈希集合，可以将时间复杂度降低到 。
首先遍历数组 ，将数组中的每个元素加入哈希集合，然后依次检查从
到
的每个整数是否在哈希集合中，不在哈希集合中的数字即为丢失的数字。由于哈希集合的每次添加元素和查找元素的时间复杂度都是
，因此总时间复杂度是
。
代码
class Solution {
func missingNumber(_ nums: [Int]) -> Int {
let set: Set<Int> = Set(nums)
for i in 0...nums.count {
if !set.contains(i) {
return i
}
}
return -1
}
}
复杂度分析
时间复杂度：
空间复杂度：
方法三：位运算
思路及解法
数组 中有
个数，在这
个数的后面添加从
到
的每个整数，则添加了
个整数，共有
个整数。
在 个整数中，丢失的数字只在后面
个整数中出现一次，其余的数字在前面
个整数中（即数组中）和后面
个整数中各出现一次，即其余的数字都出现了两次。
根据出现的次数的奇偶性，可以使用按位异或运算得到丢失的数字。按位异或运算 满足交换律和结合律，且对任意整数
都满足
和
。
由于上述 个整数中，丢失的数字出现了一次，其余的数字都出现了两次，因此对上述
个整数进行按位异或运算，结果即为丢失的数字。
代码
class Solution {
func missingNumber(_ nums: [Int]) -> Int {
var res = 0
for i in 0..<nums.count {
res ^= nums[i]
}
for i in 0...nums.count {
res ^= i
}
return res
}
}
复杂度分析
时间复杂度：
个数字计算按位异或的结果。
空间复杂度：
。
方法四：数学
思路及解法
将从 到
的全部整数之和记为
，根据高斯求和公式，有：
将数组 的元素之和记为
，则
比
少了丢失的一个数字，因此丢失的数字即为
与
之差。
代码
class Solution {
func missingNumber(_ nums: [Int]) -> Int {
var n: Int = nums.count
var total: Int = n * (n + 1) / 2
for i in 0..<nums.count {
total -= nums[i]
}
return total
}
}
复杂度分析
时间复杂度：
空间复杂度：
