268. Missing Number.md

title	toc	date	tags	top
268. Missing Number	false	2017-08-17	Leetcode Array Math Bit Manipulation	268

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?

分析

题目给定的数列的范围是$0\sim n$，由于$n$是已知的(n=nums.length)，所以数列的和也是已知的。那么把给定数组加起来得到总和，减小的部分就是缺失的数字。

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

另一种好的方法是使用位操作。原本一共有$n+1$个数字0, 1, 2, ..., n。数组一共有$n$个数，数组的下标也有$n$个数。如果数组是全的话(有$n+1$个数字)，数组中的数字和下表按位异或的结果应该等于0。现在缺失一个数字，那么按位异或的结果肯定就等于缺失的数字。

public int missingNumber(int[] nums) {
    int n = nums.length;
    int res = 0;
    res ^= n; // 异或数组下标n
    for (int i = 0; i < n; i++)
        res ^= i ^ nums[i]; // 异或数组下标和数组中的数
    return res;
}