C++ Coding Exercise – Find All Duplicates in an Array

learn-to-code

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements that appear twice in this array. Could you do it without extra space and in O(n) runtime? Example:
Input:
[4,3,2,7,8,2,3,1]
Output:
[2,3]

We can use a hash table i.e. unordered_set in C++ to check if a number has appeared before. The time complexity is O(n) and the space complexity is also O(n) via using the set data structure – which is O(1) in both inserting and lookup.

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

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> r;
        unordered_set<int> hash;
        for (const auto &n: nums) {
            if (hash.count(n)) {  // if it has appeared before
                r.push_back(n);
            } else {
                hash.insert(n);  // put it in hash
            }
        }
        return r;
    }
};

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> r;
        unordered_set<int> hash;
        for (const auto &n: nums) {
            if (hash.count(n)) {  // if it has appeared before
                r.push_back(n);
            } else {
                hash.insert(n);  // put it in hash
            }
        }
        return r;
    }
};

As stated, the input numbers are all ranged from 1 to n where n is the size of the array. We can mark the number by turning the corresponding element at index [number] negative. If it has been negative already, we know it appears before.

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

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> r;
        for (auto i = 0; i < nums.size(); ++ i) {
            if (nums[abs(nums[i]) - 1] < 0) {  // marked as appeared
                r.push_back(abs(nums[i]));
            } else {
                nums[abs(nums[i]) - 1] = -nums[abs(nums[i]) - 1];
            }
        }
        return r;
    }
};

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> r;
        for (auto i = 0; i < nums.size(); ++ i) {
            if (nums[abs(nums[i]) - 1] < 0) {  // marked as appeared
                r.push_back(abs(nums[i]));
            } else {
                nums[abs(nums[i]) - 1] = -nums[abs(nums[i]) - 1];
            }
        }
        return r;
    }
};

This is done in-place, so O(1) space complexity and O(n) one pass time complexity.

You may also like: C++编程练习题：找出数组中所有重复的元素

–EOF (The Ultimate Computing & Technology Blog) —