leetcode268 Missing Number-zh
# 268. 丢失的数字 (opens new window)
English Version (opens new window)
# 题目描述
给定一个包含 [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 中。
提示：
n == nums.length1 <= n <= 1040 <= nums[i] <= nnums中的所有数字都 独一无二
# 解法
异或求解。两个相同的数异或的结果为 0。
也可以用数学求解。求出 [0..n] 的和，减去数组中所有数的和，就得到了缺失的数字。
# Python3
class Solution:
def missingNumber(self, nums: List[int]) -> int:
res = len(nums)
for i, v in enumerate(nums):
res ^= (i ^ v)
return res
1
2
3
4
5
6
2
3
4
5
6
# Java
- 异或
class Solution {
public int missingNumber(int[] nums) {
int res = nums.length;
for (int i = 0, n = res; i < n; ++i) {
res ^= (i ^ nums[i]);
}
return res;
}
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
- 数学
class Solution {
public int missingNumber(int[] nums) {
int res = nums.length;
for (int i = 0, n = res; i < n; ++i) {
res += (i - nums[i]);
}
return res;
}
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# ...
1
编辑 (opens new window)
上次更新: 2021/10/30, 12:58:38