LeetCode 217. Contains Duplicate
LeetCode 217. Contains Duplicate
LINK: https://leetcode.com/problems/contains-duplicate/
Matter
You are given an integer array.
Check whether any element appears more than once.
Return true if at least one duplicate exists, otherwise return false.
Example.
[1]
Input:
nums = [1,2,3,1]
Output:
true
Explanation:
The value 1 appears multiple times.
[2]
Input:
nums = [1,2,3,4]
Output:
false
Explanation:
All elements are unique.
[3]
Input:
nums = [1,1,1,3,3,4,3,2,4,2]
Output:
true
Explanation:
There are multiple duplicated values.
Constraints
1 <= nums.length <= $10^5$
-$10^9$ <= nums[i] <= $10^9$
Problem analysis
A brute-force approach would compare each element with every other element, which results in $O(n^2)$ complexity and is inefficient for large inputs.
A more optimal approach is to track elements as we iterate.
If an element has already been seen before, we can immediately conclude that a duplicate exists.
This allows us to solve the problem in a single pass.
Solution
Hash but slow (40 ~ 50ms)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution
{
public:
bool containsDuplicate(std::vector<int>& nums)
{
bool bReturn = false;
do
{
std::unordered_map<int, int> mapNums;
for(int& i32Value : nums)
{
auto iter = mapNums.find(i32Value);
if(iter != mapNums.end())
{
bReturn = true;
break;
}
mapNums[i32Value] = 1;
}
}
while (false);
return bReturn;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution
{
public:
bool containsDuplicate(std::vector<int>& nums)
{
bool bReturn = false;
do
{
std::unordered_set<int> setNums;
for(int& i32Value : nums)
{
auto iter = setNums.find(i32Value);
if(iter != setNums.end())
{
bReturn = true;
break;
}
setNums.insert(i32Value);
}
}
while (false);
return bReturn;
}
};
Sort and fast (17 ~ 23ms)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution
{
public:
bool containsDuplicate(std::vector<int>& nums)
{
bool bReturn = false;
do
{
std::sort(nums.begin(), nums.end());
for(int i = 0; i < int(nums.size()) - 1; ++i)
{
if(nums[i] == nums[i+1])
{
bReturn = true;
break;
}
}
}
while (false);
return bReturn;
}
};