LeetCode - 268. Missing Number

Question

题目

解析

题目要求在 O(n) 时间和 O(1) 空间内完成。
也是一个很有意思的题目，简单的想法:

• 用一个变量 sumAll 记录包含没有丢失的那个数的所有的和（也可以用等差数列求和公式求出)；
• 然后求出数组的和 sum ，结果就是 sumAll - sum ；

更好的解法，利用亦或的性质：

利用第四条性质，循环亦或 xor = xor ^ (i+1) ^ nums[i] 其中没有出现的数就会剩下来。

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

用等差数列求和公式求出 sumAll ：

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

更加巧妙的方式，利用异或运算：

class Solution {

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