题目

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

Example 1:

Input: [3,0,1]

Output: 2

Example 2:

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

Output: 8

解法一

思路

我们直接求出数组中所有元素之和，然后用 应有的和 减去 目前元素之后，得到的结果就是缺的那个数字。

应有的和怎么求呢？其实就是len*(len+1)/2。因为如果数组中有9个元素，那么加上缺的数字，一共有从0到9这10个元素，也就是 (len+1)(len+0)/2。

代码

class Solution {    public int missingNumber(int[] nums) {        int sum = 0;        int len = nums.length;        for(int i = 0; i < len; i++) {            sum += nums[i];        }        return len*(len+1)/2 - sum;    }}

解法二

思路

用位运算。运用java中的异或来解题。异或性质如下：

1、交换律

2、结合律（即(a^b)^c == a^(b^c)）

3、对于任何数x，都有x^x=0，x^0=x

4、自反性 A XOR B XOR B = A xor 0 = A

所以我们将缺少数字的数组和应有的数组异或一遍，最后的结果就是我们要找的数字。

代码

class Solution {    public int missingNumber(int[] nums) {        int res = 0;        for(int i = 0; i < nums.length; i++) {            res ^= nums[i] ^ (i + 1);        }        return res;    }}

解法三

思路

可以先将数字排序，然后用二分查找法。

代码

class Solution {    public int missingNumber(int[] nums) {        Arrays.sort(nums);        int left = 0;        int right = nums.length - 1;        while(left <= right) {            int mid = left +(right-left)/2;            if(nums[mid] > mid) right = mid-1;            else left = mid + 1;        }        return left;    }}