【leetcode】217. 存在重复元素

题目内容

思路分析

本题是一道调节心态题（做完我又觉得我行了😂）

主要思路为使用一个set来记录每个数字出现的次数，当发现有数字的出现次数大于1时，则证明存在重复元素，返回true；遍历完数组还未返回，则证明不存在重复元素，返回false。

另外，看题目的评论区有人说

来了，来了。面试经典问题，map底层是什么数据结构

就去搜索了一下C++常见容器对应的底层数据结构：

容器	底层数据结构
vector	数组
map / multimap / set / multiset	红黑树
unordered_map / unordered_multimap / unordered_set / unordered_multiset	哈希表
priority_queue	堆

代码

#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>

using namespace std;

class Solution {
public:
    // 自己的解，时间复杂度O(N)，空间复杂度O(N)
    bool containsDuplicate1(vector<int>& nums) {
        unordered_map<int, unsigned int> count;
        
        for (auto num : nums) {
            if ((++count[num]) > 1) return true;
        }
        return false;
    }

    // 官方解，时间复杂度O(N)，空间复杂度O(N)
    // 但是没有用map，也没有必要用map，占用的空间会更小
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> count;

        for (auto num : nums) {
            auto result = count.insert(num);
            if (!result.second) return true;
        }
        return false;
    }
};


int main() {
    Solution s;
    vector<int> input{ 1,2,5,6,6 };

    bool output;
    output = s.containsDuplicate(input);

    return output;
}

收获

提升了信心
了解了下C++常见容器对应的底层数据结构