Leetcode [268] --Missing Number

Note:Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
Tags : Array ,Math , Bit Manipulation
Difficulty: Medimum
Classification: Bit Manipulation

2. 问题翻译

从0~n之间取出n个不同的数字，找出其中丢失的那个数。例如，nums = [0，1，3] ，缺失的是 2。
要求算法时间复杂度是O(n)，且只占用很少的额外空间。

3. 解题分析

在解决算法题之前，对问题进行准确的分析是设计良好解决方案的基础，从题干中提取出有价值信息的能力是我们刷题锻炼的目的之一。

0~n中取n个数，找出缺失的那个数

这句话中透漏出一下几点，

1 . 数组中元素个数为 n
2 . 0~n 总共有(n+1)个数，而实际只有n个，二者之间相差一个数
3 . 题目未指明元素是否有序
以上是能够从题目得到关键信息。

对于这种题目，我们脑海里面的第一解题思路是，排序->对比，但最快的排序算法时间复杂度也是O(nlogn)，不符合题目线性时间的要求。
上一个思路行不通，那么我们就要考虑别的方式，根据第二点信息，等价于告诉我们，有两个序列0~n和0~n序列的子集，二者相差一个数，怎么确定少了哪个数呢？到了这个地步，很明显我们可以对两个序列分别累加求和，将前者的总和减去后者总和即是丢失的那个数，再来看下是否满足要求，0~n求和属于连续自然数求和，我们可以直接套用数列公式，
1.自然数求和公式

时间复杂度为O(1),而第二个序列求和，只能通过循环来进行计算，时间复杂度为O(n),该算法总的时间复杂度为O(n)，符合题目要求，那么剩下的就是编码的问题了。
思路二
题目的tag中含有bit manipulation,即本题可以采用位操作来解决，根据情况可用的位运算，唯有XOR亦或运算，它的特点是，相同为0，不同为1；那么我们可以利用这个规律去解决问题，对两个序列0~n 和 0~n 的子集中的元素，依次进行亦或运算，之后将两个结果再次进行亦或，那么得到结果就时第二个序列中缺少的那个元素。原因是因为将亦或的原理进行推广，将一组数依次异或，若里面只有一个只出现一次的数，其他的数都出现两次，则最后的结果必然是那个只出现一次的数，因此就可以得到缺少的那个元素。对于这个算法，只需要进行两次循环，每次循环的时间复杂度是O(n)，空间复杂度为O(1)，符合题目要求。具体步骤分解如下：

1 . 0~n 所有元素(包括0和n) XOR，记做x
2 . nums 所有元素XOR，从nums[0] 开始，结果记做y
3 . x 和 y 进行 XOR，最后结果返回

4. 解题方案

Solution 1：

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        unsigned int n = nums.size();
        int total =  n*(n+1)/2;
        for(int i = 0; i < n;++i)
            total -= nums[i];
        return total;
    }
};

Solution 2 ：

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

转载请注明出处： http://www.jianshu.com/p/b14ca0d7ad86