How to Find Intersection of Two Arrays in C++?


Question: Write a function to return the intersection of two arrays: For example, the intersection of [1, 2, 2, 1] and [2, 2] returns [2]. The return array should only contain unique numbers and the order does not matter.

Using STL, we can have two sets, one for recording the first array, the other for checking duplicates in the output array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> nums;
        for (auto x: nums1) { 
            nums.insert(x);
        }
        vector<int> r;
        unordered_set<int> dup;
        for (auto x: nums2) {
            if (nums.count(x)) {
                if (!dup.count(x)) { // no duplicates
                    r.push_back(x);    
                }   
                dup.insert(x);
            }
        }
        return r;
    }
};
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> nums;
        for (auto x: nums1) { 
            nums.insert(x);
        }
        vector<int> r;
        unordered_set<int> dup;
        for (auto x: nums2) {
            if (nums.count(x)) {
                if (!dup.count(x)) { // no duplicates
                    r.push_back(x);    
                }   
                dup.insert(x);
            }
        }
        return r;
    }
};

However, we can use only 1 set to solve this problem. Once a number is added to output, we remove this from the set so it won’t be added back again for future duplicate numbers.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> nums;
        for (auto x: nums1) {
            nums.insert(x);
        }
        vector<int> r;
        for (auto x: nums2) {
            if (nums.count(x)) {
                r.push_back(x);    
                nums.erase(x);  // removed from set
            }
        }
        return r;
    }
};
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> nums;
        for (auto x: nums1) {
            nums.insert(x);
        }
        vector<int> r;
        for (auto x: nums2) {
            if (nums.count(x)) {
                r.push_back(x);    
                nums.erase(x);  // removed from set
            }
        }
        return r;
    }
};

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
268 words
Last Post: Dynamic Programming - How many ways to connect the pipes?
Next Post: Writing Unit Tests in VBScript

The Permanent URL is: How to Find Intersection of Two Arrays in C++?

6 Comments

  1. rieeez
  2. riez
      • riez
  3. fariez

Leave a Reply