This is the 15th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

preface

The intersection of two arrays II is similar to LeetCode 349, but different from LeetCode 349. In this article, we will use hash tables to solve this problem

Topic describes

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

Example 1:

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

Output: [2]

Example 2:

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

Output: [4, 9]

Description:

The number of occurrences of each element in the output should be the same as the minimum number of occurrences of the element in both arrays. We can ignore the order of the output.

Their thinking

  • The intersection of two arrays is the same item in both arrays
  • First order Pointers are ordered by the two arrays, and then declare a and b two Pointers, points to two arrays respectively, and then began to move, or three conditions, if a referred to in item is greater than b refers to the item, then b pointer, if less than referred to in item b has pointed out, then move a pointer, if the pointer is a pointer and b refers to the same, Push into the result array, and the a and B Pointers move at the same time until the end
  • Hash table is a loop through which all the items in an array are stored into a hash table, where the values are the keys in the hash table, and the values in the hash table are the number of occurrences of the same array, that is, If the first array is [1,2,3,3,1], the result will be {1:2,2:1,3:2}. Then loop through the second array, get each item to see if it exists in the hash table. If it does, push into the result array and subtract the corresponding key value by one until the end. So this is the value of result and that’s what we’re looking for. So here’s the code
/ * * *@param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}* /
var intersect = function(nums1, nums2) {
    let map = {} // Declare a hash map to store the number of occurrences of each array in nums1
    let result = []
    for(let num1 of nums1){ // Insert each item in nums1 into the map
        if(map[num1]){
            map[num1]++
        }else{
            map[num1] = 1}}for(let num2 of nums2){
        if(map[num2]>0) {// A value greater than 0 indicates that the current array already exists in the map, i.e. nums1 contains this number
            result.push(num2)
            map[num2]--
        }
    }
    return result
};
Copy the code

conclusion

Hash map data structure features to solve the problem, the problem solution method is more, I use hash table to solve because this method is not commonly used, here contact, if there are ideas welcome comments, gogogo!!