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

For example,

Given nums = [0, 1, 3] return 2.

找出丢失的整数

 

解题思路1：

用1到n的和减去数组中的数字之和就是丢失的数。时间复杂度是O(n)，空间复杂度是O(1)

public class Solution {    public int missingNumber(int[] nums) {        int sum = 0, n = nums.length;        for (int num : nums)             sum += num;                return n*(n+1)/2 - sum;    }}

 

解题思路2：

利用异或运算，由于a^b^b = a；因此将所有的下标与对应的数组中的数异或，留下的数即丢失的数。例如一个数组是[0,1,2,4,5]，将0,1,2,4,5和0,1,2,3,4,5异或，留下3，即缺失的数字。

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