3.5刷题记录 Missing Number(268)

3.5刷题记录 Missing Number(268)

 

 3.5刷题记录 Missing Number(268)

 

 很简单的题,会用哈希表即可,将哈希表存入出现过的元素,再一个个遍历未出现的元素,如果不用哈希表的话复杂度会增高。

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;
    }
};

 

上一篇:LeetCode 1 两数之和


下一篇:c++ map与unordered_map区别及使用