Leetcode 268 - Missing Number（等差数列 or 位运算）

题意

给一个大小为n的数组，里面的元素为[0, n]中缺了一个数字，求缺的那个数字。

要求：

思路

算法1

如果数组包含[1, n]那么它的和为n(n+1)2$/frac{n(n+1)}{2}$。那么我们现在只需要对数组求和，两个相减，得到的就是缺失的那个数字了。

算法2

利用异或。

我们知道^为：1 ^ 1 = 0, 0 ^ 1 = 1。

那么，就可以得到这样两个结论：

然后，对于这道题，我们可以另x1 = 0 ^ 1 ^ 2 ^ ....^ n，x2 = a[0] ^ a[0] ^...a[n - 1]

最后，我们用x1 ^ x2，可以知道：如果一个数y在a[]中出现过，假设为ak$a_k$，那么y ^ a[k] = 0。

基于这个思想，假设我们没有出现的数是z，那么我们最后x1 ^ x2的结果即为：0 ^ z = z。

代码