tags:
  - DSA

L1. Contains Duplicate

Description

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Solution

为了检查数组中的元素是否存在重复，使用 std::unordered_set 看上去很不错。尽管 std::set 也可以完成此任务，并且红黑树能够提供的增删查改时间复杂度，但在题目描述的情景下 std::unordered_set 通过平均的插入和查找性能表现得更为优异。

如果检查的数据量极大（上亿）使用 std::set 会不会更好呢？

#include <iostream>
#include <vector>
#include <unordered_set>

class mySolution{
public:
    bool checkDuplication(const std::vector<int>& v){
        std::unordered_set<int> set;
        for(int elem : v){
            if(set.count(elem)){ return true; }
            // if(set.contains(elem)){ return true; } // C++20
            set.insert(elem);
        }
        return false;
    }
};

int main(){
    std::vector<int> v1 = {1,2,3,4,9,7,2};
    std::vector<int> v2 = {1,2,4,5,10,59,66,100,15,20,5,10};
    std::vector<int> v3 = {1,2,3,4,5,6,7,8,9,10};
    mySolution solution;
    std::cout << (solution.checkDuplication(v1) ? "Find!\n" : "Not Find!\n")
              << (solution.checkDuplication(v2) ? "Find!\n" : "Not Find!\n")
              << (solution.checkDuplication(v3) ? "Find!\n" : "Not Find!\n")
              << std::endl;
    return 0;
}