Egbert Lin's Blog

“Life is not a race, but a journey to be savoured each step of the way” by Brian Dyson

[LeetCode Road] Contains Duplicate - Solution/C++

Posted on Edited on In Disqus:

217. Contains Duplicate

Question:

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.

Example:

Input: [1,2,3,1]
Output: true

Input: [1,2,3,4]
Output: false

Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

Source code

Version 1

Idea:
You can use unordered_map to store elements in container. At 7 line, use count() to return 1 or 0. If return 0, it means the nums[i] cannot find, so you can insert it. Otherwise, it means the nums[i] has exist already, return true.

Time complexity: O(n)
Space complexity: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_map<int, int> record;
        
        for(int i = 0; i < nums.size(); i++){
            if(!record.count(nums[i])){
                record.insert(make_pair(nums[i], 0));
            }else{
                return true;
            }
        }
        return false;
    }
};

Version 2

Idea:
Each element is inserted only if it is not equivalent to any other element already in the container (elements in an unordered_set have unique values) by using unordered_set.
As mentioned above, an unordered_set can effectively increases the container size by the number of elements inserted.[1]

At 6 line, it can refered to pair<iterator,bool> insert ( const value_type& val );, the function returns a pair object:
  • First element: an iterator pointing either to the newly inserted element in the container or to the element whose key is equivalent.
  • Second element: a bool value indicating whether the element was successfully inserted or not.

So, if record.insert(nums[i]).second returns 0, it represented nums[i] has been inserted in container, return true.

Time complexity: O(n)
Space complexity: O(n)

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> record;
        for(int i = 0; i < nums.size(); i++)
            if(!record.insert(nums[i]).second) return true;
        
        return false;
    }
};

Version 3

Idea:
An optiaml and efficient approach by using sorting.
At first, use std::sort() to get an array in order. Then, check current element i and next element i+1 whether they are the same or not. If they are the same, return true, otherwise, return false until for loop is end.

What is std::sort()?
The algorithm used by sort() is IntroSort. Introsort being a hybrid sorting algorithm uses three sorting algorithm to minimise the running time, Quicksort, Heapsort and Insertion Sort.[2]

Time complexity: O(nlogn)
Space complexity: O(1)

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

Reference:
[1] https://www.cplusplus.com/reference/unordered_set/unordered_set/insert/
[2] https://www.geeksforgeeks.org/internal-details-of-stdsort-in-c/