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
Note: Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
class Solution {
public int missingNumber(int[] nums) {
int len = nums.length;
int sum = (1+len)*len/2;
int arraySum = 0;
for(int num : nums){
arraySum += num;
}
return sum - arraySum;
}
}class Solution {
public int missingNumber(int[] nums) {
int res=0;
for(int i=0;i<nums.length;i++){
res^=(i+1)^nums[i];
}
return res;
}
}方法一：
因为缺少了一个数字，所以可以求和再减去数组的和就是剩下的缺失数字。
方法二：
让0到n（即nums.length）和数组中的所有数进行异或运算，最后得到的结果就是缺失的数。