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

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

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

推荐阅读：
让新浪微博变身外链图床的wordpress插件：微博图床　 三款自动翻译文章标题为英文的wordpress插件介绍与比较　 WodrPress实现远程图片本地化插件-Auto_Save_Image　 碧沙岗公园作文　 世界的奇迹作文700字　 初有所成，静待花开　 端午包粽子作文350字　 成长的温暖作文900字　 沙家浜作文400字　 中秋节作文1400字：思念在那个秋天　
评论列表
添加评论