[LeetCode]Missing Number

这道题用我们之前First Missing Positive的方法或者二分都可以做。但其实有更简单的方法，我们先讨论二分，因为我们知道答案的范围，所以我们可以在值域上做二分，每次去原数组验证，然后根据结果决定选择哪个子区间，时间复杂度O(n * log n)，常数空间，代码如下：

	class Solution {
	public:
	int missingNumber(vector<int>& nums) {
	int n = nums.size(), lo = 0, hi = n;
	while(lo < hi)
	{
	int mid = lo + (hi - lo) / 2, count = 0;
	for(auto& num : nums)
	if(num <= mid)
	++count;
	if(count == mid + 1)
	lo = mid + 1;
	else
	hi = mid;
	}
	return lo;
	}
	};

view raw Missing Number_2.cpp hosted with ❤ by GitHub

但其实这道题和我们之前做的Single Number是一样的，区别是这里只给了你一半的数，我们补上另一半就行了，然后XOR位操作即可，linear time，代码如下：

	class Solution {
	public:
	int missingNumber(vector<int>& nums) {
	int missingN = 0;
	for(auto& num : nums)
	missingN ^= num;
	for(int i = 0; i <= nums.size(); ++i)
	missingN ^= i;
	return missingN;
	}
	};

view raw Missing Number_1.cpp hosted with ❤ by GitHub