Leetcode [268] --Missing Number
1. 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?
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求和属于连续自然数求和，我们可以直接套用数列公式，
自然数列求和
时间复杂度为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;
}
};
