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

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

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

推荐阅读：
召公谏厉王止谤原文及翻译　 百家讲坛系列节目《于丹〈论语〉心得》MP3蓝奏云下载　 吴许越成原文及翻译　 诗词名句鉴赏：我所思兮在太山，欲往从之梁父艰。　 诗词名句鉴赏：大风起兮云飞扬，威加海内兮归故乡。　 百家讲坛系列节目《于丹〈庄子〉心得》MP3蓝奏云下载　 诗词名句鉴赏：男儿爱后妇，女子重前夫。　 诗词名句鉴赏：居异土国兮心内伤，愿为黄鹄兮归故乡。　 子革对灵王原文及翻译　 写人作文乐趣作文900字　
评论列表
添加评论