268. Missing Number

Description

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

Example 1

1
2
Input: [3,0,1]
Output: 2

Example 2

1
2
Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Solution

传统思维（O(n)的空间复杂度）：使用哈希的思想，试图用数组等结构记录那些数已经出现过。

优秀解法（O(1)的空间复杂度）：

1.利用亦或运算的特性：同一个数亦或两次抵消。因此开始可以先置初值0，然后将每个数[0,n]亦或一遍，再将数组中的每个数亦或一遍。因此数组中出现的数最终会被亦或两遍，而只有“Missing Number”最终只会被亦或一遍。由于初值是0，亦或两遍后留存的值即是“Missing Number”。

2.利用加和：利用高斯求和公式求出如果每个数都有的情况下的加和，再逐个减去数组中出现的数，最终得到“Missing Number”。