题目描述:
给定一个包含 [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.length - 1 <= n <=
-
0 <= nums[i] <= n -
nums 中的所有数字都 独一无二
题目分析:
这道题其实是 LeetCode 136.只出现一次的数字(简单) 的变形题，基本思路一致，都是使用异或运算的特点 x ^ x = 0 和 x ^ 0 = x 解题。例如给出一个数组 [0, 1, 3] ，数组长度为 3 ，缺了 2 这个数，那么我们就把数组的所有索引值以及数组中的每个值进行异或操作，最后再与数组长度进行异或，就能得到答案。这个例子异或表达式为 (0 ^ 1 ^ 2) ^ (0 ^ 1 ^ 3) ^ 3 = 2 。
题解:
执行用时: 0 ms
内存消耗: 38.8 MB
class Solution {
public int missingNumber(int[] nums) {
// 结果 初始化为数组长度值
int res = nums.length;
// 将数组中的每个数和对应索引进行异或，得到结果与 res 异或
for (int i = 0; i < nums.length; ++i) {
res ^= i ^ nums[i];
}
// 返回结果
return res;
}
}题目来源:力扣(LeetCode)