268. 丢失的数字--java-异或运算

1. 丢失的数字

给定一个包含 [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 <= 104
0 <= nums[i] <= n
nums 中的所有数字都 独一无二

在这里插入图片描述

这里采用了异或运算，那么，什么是异或运算呢 异或的运算方法是一个二进制运算: a ^ b 将其转为二进制，然后每一位都进行比较，两者相等为0,不等为1，得到的就是异或运算的结果。 例如： 2 ^ 4 = 6 解释： 0010 ******* = 0110 = 6 0100

异或运算法则

1. a ^ b = b ^ a
2. a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c;
3. d = a ^ b ^ c 可以推出 a = d ^ b ^ c.
4. a ^ b ^ a = b.

n^0=n n^n=0，即任何数与0进行异或，为它本身，两个相同的数进行异或运算，会得到0。

那么参照上面的解释，这个题即 找出 1到n 中，少的那一个

由于1 ^ 2 ^ 3 …^ n ^ 0 ^ 1 ^ 2 ^ 3…^ (n-1) = n 所以就得到了这题的答案：如上图