missing-number

Missing Number – LeetCode 268

Problem

Description

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

Answer

Original

Code

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i != nums.size(); ++i)
            n ^= i ^ nums[i];
        return n;
    }
};

思路

通过位操作，已知定然会有一个数字的空缺，那么可以通过异或得到，完美的One Pass方案。时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$22$ ms，排名$18.23\%$

Better

思路

没见到更好的思路了。