217. Contains Duplicate

發表於 | 分類於

problem

找出陣列中是否一個重複的數字，如果有任何數字出現至少兩次則返回true，每個數字都不同則返回false

Solution

sorting

可以先sort 是否有前後兩元素相同

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for(int i=1;i<n;++i){
            if(nums[i] == nums[i-1]) return true;
        }
        return false;
        
    }
};

hash table

set or map

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> s;
        for(int n:nums){
            if(s.count(n)) return true;
            s.insert(n);
        }
        return false;

        // return !(nums.size()==unordered_set<int>(nums.begin(),nums.end()).size());
    }
};

analysis

  • sorting
    • time complexity O(nlogn)
    • space complexity O(1)
  • hash table
    • time complexity O(n) assuming set find operation cost const time
    • space complexity O(n)