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

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

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) —

推荐阅读：
如何让wrodpress在分类列表页显示其下子分类文章列表　 如何下载WordPress官网插件的旧版本　 剧场有多少座位　 荷叶覆盖面积正好占池塘面积的四分之一　 世界杯一共要进行多少场比赛　 浓度问题　 第二天生产的比总数的1/4少30个　 这题出给小学生做合适吗？　 两个正方形的面积分别是4平方厘米和36平方厘米　 原来两人共有多少钱　
评论列表
添加评论