Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
The best solution is to use a hash map or hash set that performs a O(1) complexity in inserting, and lookup.
1 2 3 4 5 6 7 8 9 10 11 12 13 | class Solution { public: bool containsDuplicate(vector<int>& nums) { unordered_set<int> cache; for (int i = 0; i < nums.size(); i ++) { if (cache.count(nums[i])) { return true; } cache.insert(nums[i]); } return false; } }; |
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> cache;
for (int i = 0; i < nums.size(); i ++) {
if (cache.count(nums[i])) {
return true;
}
cache.insert(nums[i]);
}
return false;
}
};Simple O(n) solution uses the std::unordered_set. If at any time, the integer appears twice in the set, the function quits with true.
--EOF (The Ultimate Computing & Technology Blog) --
GD Star Rating
loading...
183 wordsloading...
Last Post: How to Merge Two Sorted Lists (Recursion and Iterative)?
Next Post: C++ Coding Exercise - Majority Element
