The Intersection Algorithm of Two Arrays using Hash Maps in C++/

  • 时间：2020-10-11 16:01:36
  • 分类：网络文摘
  • 阅读：111 次

Given two arrays, write a function to compute their intersection.

Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]

Note:
Each element in the result should appear as many times as it shows in both arrays.
The result can be in any order.

Follow up:
  • What if the given array is already sorted? How would you optimize your algorithm?
  • What if nums1’s size is small compared to nums2’s size? Which algorithm is better?
  • What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

To compute the intersection of two arrays, we can use a hash map to record the number of times that each element appears in the first array. This takes O(N) time and O(N) space complexity.

Once we have recorded the elements in the HashMap, we can iterate over the second array, and check if the number corresponding to the hashmap. We need to push the element to the result array and decrement the counter. If the counter for the element becomes zero, we don’t count it as intersection.

How to compute the Array intersection in C++?

In C++, we use unordered_map to declare a hash map. We use find to check if an element appears in the hash map.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> r;
        unordered_map<int, int> count;
        for (const auto &n: nums1) {
            if (count.find(n) == count.end()) {
                count[n] = 1;
            } else {
                count[n] ++;
            }
        }
        for (const auto &n: nums2) {
            if (count.find(n) != count.end()) {
                if (count[n] > 0) {
                    r.push_back(n);
                    count[n] --;
                }
            }
        }
        return r;
    }
};
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> r;
        unordered_map<int, int> count;
        for (const auto &n: nums1) {
            if (count.find(n) == count.end()) {
                count[n] = 1;
            } else {
                count[n] ++;
            }
        }
        for (const auto &n: nums2) {
            if (count.find(n) != count.end()) {
                if (count[n] > 0) {
                    r.push_back(n);
                    count[n] --;
                }
            }
        }
        return r;
    }
};

How to get array intersection in Java?

Unfortunately, Java is a bit verbose. To convert a List of integers to Array, we need to use the following:

1

list.stream().mapToInt(Integer::intValue).toArray();
list.stream().mapToInt(Integer::intValue).toArray();

The following Java implementation is based on the same algorithm.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        List<Integer> r = new ArrayList<Integer>();
        HashMap<Integer, Integer> count = new HashMap<Integer, Integer>();
        for (int n: nums1) {
            if (!count.containsKey(n)) {
                count.put(n, 1);
            } else {
                count.put(n, count.get(n) + 1);
            }
        }
        for (int n: nums2) {
            if (count.containsKey(n)) {
                if (count.get(n) > 0) {
                    r.add(n);
                    count.put(n, count.get(n) - 1);
                }
            }
        }
        return r.stream().mapToInt(Integer::intValue).toArray();
    }
}
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        List<Integer> r = new ArrayList<Integer>();
        HashMap<Integer, Integer> count = new HashMap<Integer, Integer>();
        for (int n: nums1) {
            if (!count.containsKey(n)) {
                count.put(n, 1);
            } else {
                count.put(n, count.get(n) + 1);
            }
        }
        for (int n: nums2) {
            if (count.containsKey(n)) {
                if (count.get(n) > 0) {
                    r.add(n);
                    count.put(n, count.get(n) - 1);
                }
            }
        }
        return r.stream().mapToInt(Integer::intValue).toArray();
    }
}

JavaScript Array Intersection Algorithm

We use array.forEach to go through each element in JavaScript array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function(nums1, nums2) {
    var data = {};
    nums1.forEach(function(n) {
        if (!data[n]) {
            data[n] = 1;
        } else {
            data[n] ++;
        }        
    });
    var r = [];
    nums2.forEach(function(n) {
        if (data[n] && data[n] > 0) {
            r.push(n);
            data[n] --;
        }    
    });
    return r;
};
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function(nums1, nums2) {
    var data = {};
    nums1.forEach(function(n) {
        if (!data[n]) {
            data[n] = 1;
        } else {
            data[n] ++;
        }        
    });
    var r = [];
    nums2.forEach(function(n) {
        if (data[n] && data[n] > 0) {
            r.push(n);
            data[n] --;
        }    
    });
    return r;
};

You can also use the Sort and Two Pointer algorithm: How to Compute the Intersection of Two Arrays using Sorting + Two Pointer Algorithm?

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
高帝求贤诏原文及翻译　 报任少卿书/报任安书原文及翻译　 太史公自序原文及翻译　 货殖列传序原文及翻译　 当生命离开我的时候作文800字　 打苍蝇作文100字　 描写莲花湖的作文　 是冬成就了雪，还是雪美丽了冬　 让我们走向海洋作文350字　 圣诞节的作文500字　
评论列表
添加评论