268.丢失的数字
题目描述
给定一个包含 [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 中。
思路
- 一次遍历
遍历0~n的数字，如果不在nums数组中，则将其返回。 - 排序
将数组排序之后，即可根据数组中每个下标处的元素是否和下标相等，得到丢失的数字。
注：如果长度为n的数组（下标为0~n-1）元素与下标都相等，则丢失元素为n - 位运算
数组 nums 中有 n 个数，在这 n 个数的后面添加从 0 到 n 的每个整数，则添加了 n+1 个整数，共有 2n+1 个整数。
在 2n+1 个整数中，丢失的数字只在后面 n+1 个整数中出现一次，其余的数字在前面 n 个整数中（即数组中）和后面 n+1 个整数中各出现一次，即其余的数字都出现了两次。
根据出现的次数的奇偶性，可以使用按位异或运算得到丢失的数字。按位异或运算^满足交换律和结合律，且对任意整数 x 都满足 x^x=0 和 x^0=x。
由于上述 2n+1 个整数中，丢失的数字出现了一次，其余的数字都出现了两次，因此对上述 2n+1 个整数进行按位异或运算，结果即为丢失的数字。 - 数学
丢失的数字 = 0~n的和 - nums数组的和代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58class Solution(object):
def missingNumber(self, nums):
"""
一次遍历
遍历0~n，如果数字不在nums中，就将它返回
:type nums: List[int]
:rtype: int
"""
for i in range(len(nums) + 1):
if i not in nums:
return i
def missingNumber1(self, nums):
"""
将数组排序之后，即可根据数组中每个下标处的元素是否和下标相等，得到丢失的数字。
注：如果长度为n的数组（下标为0~n-1）元素与下标都相等，则丢失元素为n
"""
nums.sort()
for i, num in enumerate(nums):
if i != num:
return i
return len(nums)
def missingNumber2(self, nums):
"""
位运算
"""
xor = 0
for i, num in enumerate(nums):
xor ^= i ^ num
return xor ^ len(nums)
def missingNumber3(self, nums):
"""
数学运算
"""
n = len(nums)
total = (n*(n+1)) // 2
nums_sum = sum(nums)
return total - nums_sum
if __name__ == "__main__":
slt = Solution()
nums = [3, 0, 1]
# missing_number = slt.missingNumber(nums)
# missing_number = slt.missingNumber1(nums)
# missing_number = slt.missingNumber2(nums)
missing_number = slt.missingNumber3(nums)
print(missing_number)
