LeetCode 268.Missing Number

LeetCode 268.Missing Number

Description:

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

Example 1:

Input: [3,0,1]
Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

分析：

这道题要仔细分析题目意思，说的是有n个不同的数，找出没出现的数，而这个数其实是大于等于0小于等于n的。
我们可以先给数组按从小到大排序，然后遍历一次，在循环内部利用nums[i] != i 判断没出现的数，若成立即可返回结果。
最坑的就是这个地方了：如果上述循环判断没能找到结果，记得要返回nums.size()，表示没找到n，因为题目意思是找到0-n中的一个数，是包括n的。
可能大家并没遇到这么傻的问题，但我确实在这里多提交了两次才AC。

---

代码如下：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
	int missingNumber(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		for (int i = 0; i < nums.size(); i++) {
			if (nums[i] != i) return i;
		}
		return nums.size();
	}
};
int main() {
	Solution s;
	vector<int> nums;
	int n;
	cin >> n;
	int t;
	for (int i = 0; i < n; i++) {
		cin >> t;
		nums.push_back(t);
	}
	cout << s.missingNumber(nums) << endl;
	return 0;
}