268 - Missing Number

Missing Number

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.

Hide Tags

Array Math Bit Manipulation

Hide Similar Problems

(H) First Missing Positive (M) Single Number

找一串数字丢了的那一个，最简单的方法是…… n 个数字的和 = （n+1）* n /2，减去所有的数字…… NND 竟然忘了。

上来看到 bit manipulation，就跑去数 bit 了……，
倒是按照数 bit 的方法解出来了，因为每一个bit为，都是 x 个 0，x 个 1 不断循环，
所以可以先计算出每个 bit 一共有 从 0 到 n ，一共有多少个 1， 多少个 0，然后依次减去 vector 里所有的数字，
就知道每个 bit 位缺什么了，把它们组合起来，就是答案了。

但是……这他娘的是绕弯路。。。忘了 bit manipulation 最常用的手段，叫做异或。。。
既然少了一个，那就把 vector 里所有的数字，跟 0 ~ n 之间的所有数字全部异或一次，
相同的数字互相抵消，最后的结果就是缺少的那个……

NND 任何时候 bit manipulation 都要首先想想异或！！

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int sum=0, n=nums.size();
        for(auto nn : nums)
            sum += nn;
        return n*(n+1)/2 - sum;
    }

    int missingNumber1(vector<int>& nums) {

        int rst=0, n=nums.size();
        for(int ii=0; ii<n; ++ii)
            rst = rst^nums[ii], rst=rst^ii;
        return rst^n;
    }

    int missingNumber2(vector<int>& nums) {
        int rst = 0, total=nums.size()+1;
       
        //buffers, calculate how many 0's and 1's for each bit if all numbers are existing
        int bit0sum[32]={0}, bit1sum[32]={0};
       
        //a section contains same 0's and 1's and is the smallest repeating unit of each bit
        //for example, bit 0th (lowest)'s section is {0, 1}, bit 1st's section is {0, 0, 1, 1}...
        //for each bit, check how many complete sections are there, then we can get base part of sum0/1
        //then check the incomplete sections to calculate how many 0's and 1's are there for each bit
        int sec_size=2, sec_half=1;                                     //base case for bit 0th
        bit0sum[31] = total;                                            //always 0 for any number
        for(int ii=0; ii<31; ++ii)                                      //not include highest bit
        {
            int base = (total/sec_size)*sec_half;                       //base sum
            int rest = total%(sec_size);                                //incomplete section

            bit0sum[ii] = base + ((rest>=sec_half)?sec_half:rest);      //total 0's
            bit1sum[ii] = base + ((rest>=sec_half)?(rest-sec_half):0);  //total 1's

            sec_size += sec_size;                                       //update section size
            sec_half += sec_half;                                       //update section half
        }

        for(auto n : nums)
            for(int ii=0; ii<32; ++ii)
                ((n&(1<<ii))>>ii) ? (bit1sum[ii]--) : (bit0sum[ii]--);  //reduce found bit 0/1

        for(int ii=0; ii<32; ++ii)
            if(bit1sum[ii])
                rst |= 1<<ii;                                           //rebuild missing number

        return rst;
    }
};
36 ms, 36 ms, 52 ms.