LeetCode: Contains Duplicate

Stupid Way: Cannot pass testing, too long time

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class Solution { public: bool containsDuplicate(vector<int>& nums) { for(int i=0;i<nums.size();i++){ int cur=nums[i]; int comp=i+1; while(comp<nums.size()){ if(cur==nums[comp]) return true; comp++; } } return false; } };

RedBlack tree(set): n*O(log n)

1 2 3 4 5 6 7 8 9 10 11

class Solution { public: bool containsDuplicate(vector<int>& nums) { set<int> s; for(int i=0;i<nums.size();i++){ if(s.find(nums[i])!=s.end()) return true; s.insert(nums[i]); } return false; } };

HashMap(unordered_set): n*O(1)
Tip: map element search O(log n), advantage compared to unordered_map: map is ordered
unordered_set has a convenient function count(): return 1 if key exists, 0 if not.
official definition:   Count elements with a specific key

Searches the container for elements whose key is k and returns the number of elements found. Because unordered_map containers do not allow for duplicate keys, this means that the function actually returns 1 if an element with that key exists in the container, and zero otherwise.

1 2 3 4 5 6 7 8 9 10 11

class Solution { public: bool containsDuplicate(vector<int>& nums) { unordered_set<int> s; for(int i=0;i<nums.size();i++){ if(s.count(nums[i])) return true; s.insert(nums[i]); } return false; } };

SortingWay: update later
Reference:
http://www.bubuko.com/infodetail-827176.html
http://www.cplusplus.com/reference/unordered_map/unordered_map/count/