很简单的题,会用哈希表即可,将哈希表存入出现过的元素,再一个个遍历未出现的元素,如果不用哈希表的话复杂度会增高。
class Solution { public: int missingNumber(vector<int>& nums) { int n=nums.size(); unordered_set<int>hash; for (int val : nums) { if (!set.count(val)) set.insert(val); } for (int i = 0; i <= n; ++i) { if (!set.count(i)) return i; } return -1; } };
但是也可以运用异或运算的特性解决问题。
class Solution { public: int missingNumber(vector<int>& nums) { int n = nums.size(); unordered_set<int> set; for (int val : nums) { if (!set.count(val)) set.insert(val); } for (int i = 0; i <= n; ++i) { if (!set.count(i)) return i; } return -1; } };