217. Contains Duplicate
1. Description
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.
2. Example
Example 1:
Input: [1,2,3,1]
Output: true
Example 2:
Input: [1,2,3,4]
Output: false
Example 3:
Input: [1,1,1,3,3,4,3,2,4,2]
Output: true
3. Solutions
My Accepted Solution
n = m_nums.size()
Time complexity: O($nlg_2n$)
Space complexity: O(1)
class Solution
{
public:
// bool containsDuplicate(vector<int>& nums)
bool containsDuplicate(vector<int> &m_nums)
{
sort(m_nums.begin(), m_nums.end());
for(int i = 1; i < m_nums.size(); i++)
{
if(m_nums[i] == m_nums[i-1])
return true;
}
return false;
}
};
3.1 Hash Table
n = i_nums.size()
Time complexity: O(n)
Space complexity: O(n)
class Solution
{
public:
// bool containsDuplicate(vector<int>& nums)
bool containsDuplicate(const vector<int> &i_nums)
{
map<int, int> occurTimes;
for(auto i : i_nums)
{
if(occurTimes[i] > 0)
return true;
occurTimes[i]++;
}
return false;
}
};
3.2 Set(Equal to Hash Table)
n = i_nums.size()
Time complexity: O(n)
Space complexity: O(n)
class Solution
{
public:
// bool containsDuplicate(vector<int>& nums)
bool containsDuplicate(const vector<int> &i_nums)
{
unordered_set<int> valuesSet;
for(int i = 0; i < i_nums.size(); i++)
{
if(valuesSet.find(i_nums[i]) == valuesSet.end()) valuesSet.insert(i_nums[i]);
else return true;
}
return false;
}
};