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

忘是亡心i 2023-10-08 13:04 53阅读 0赞

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 中的所有数字都 独一无二

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY4ODk3Mw_size_16_color_FFFFFF_t_70]  
这里采用了异或运算，那么，什么是异或运算呢  
异或的运算方法是一个二进制运算: 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  
所以就得到了这题的答案：如上图

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY4ODk3Mw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/efb8315f18734034a9346100308d6735.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY4ODk3Mw==,size_16,color_FFFFFF,t_70