MissingNumber [source code]

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

要求 linear, sort 肯定就不行了; 那么按照以前的总结, 首先这个 pattern 题不太像. historical stream题呢, 因为之类要求 O1 space, 要是普通的 hashmap 肯定是不行的, 要看这个历史信息怎么存取了;

想了一下就做出来了, 这个问题总体还是很简单, 用的就是类似 SingleNumber 里面的pair removal的技术.

最后的速度是2(25), 不算很快, 这个有点奇怪.
好像这个其实就是 submission最优解了, 不过可能是因为最优解太多了, 所以最后排名不够高.

不过实际上的 submission 最优解的代码用的是另外一种思路:

public class Solution {  
    public int missingNumber(int[] nums) {  
        int actualSum, foundSum = 0;  

        for(int i = 0; i < nums.length; i++) {  
            foundSum += nums[i];  
        }  

        int n = nums.length;  

        actualSum = (n * (n+1)) / 2;  

        return actualSum - foundSum;  
    }  
}

这个是之前有一题用过的 complement 的思路. 我当时有往这个方向想, 不过 bit 这个思路先出现在脑子里了.

以后如果碰到这种linear time constant space (LTCS)的题目, complement 也许也可以是一个参考的思考方向? 反正这类题目一般都是有一定的特殊性的.

这个也是一个用 bit 的做法, 不过比我的少一个 pass:

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;  
}

Problem Description

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.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Difficulty:Easy
Category:Algorithms
Acceptance:44.11%
Contributor: LeetCode
Companies
microsoft bloomberg
Related Topics
array math bit manipulation
Similar Questions
First Missing Positive Single Number Find the Duplicate Number