# 350 Intersection of Two Arrays II (有圖)

兩種方法，一個是類似桶子排序; 一個是比對重覆原本陣列值 = false

LeetCode

Given two arrays, write a function to compute their intersection.
跟 349. 交集 I 不一樣的是這題 input Array 可能會有重覆的值

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?

*/

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function(nums1, nums2) {}

怎麼解

第一個想法就是運用之前寫過的方法(我也忘了是哪題，到時候找到再補)

• forEach nums1

• 然後 nums2.indexOf(num1 item)

  • 找到代表有交集，把 item 存進 result array，然後 nums2[ num1 item ] = false，避免之後重覆找

  • 若沒找到代表這個值沒交集，在繼續找下一個

var intersect = function(nums1, nums2) {
    let result = [];
    nums1.forEach(num1 => {
        let ind = nums2.indexOf(num1)
        if(ind !== -1){
            result.push(num1);
            nums2[ind] = false;
        }
    })
    return result;
};
// faster than 66.58% of JavaScript online submissions

改善

後來看到別人解法效能更好，是類似桶子排序概念，但因為此題不但要存值還要存出現幾次，所以會用 obj 來存

• 首先會把 nums1 [4, 9, 5, 4] 存進桶子裡，value 代表次數

• 再來就是 nums2 [9,4,9,8,4] 了，他會去找 bucket 裡是否存在

  • 存在的話代表有交集，存進 result，並次數 -- (避免之後重覆存到)

  • 不存在代表沒交集，繼續下一個

result = []
buckets = {
    4: 2,
    9: 1,
    5: 1
}
nums2 = [9,4,9,8,4]
---- 開始找囉 -------
9 有在 buckets 裡
result = [9]
buckets = = {
    4: 2,
    9: 0,
    5: 1
}
------------------
4 有在 buckets 裡
result = [9, 4]
buckets = = {
    4: 1,
    9: 0,
    5: 1
}
------------------
9 沒有在 buckets 裡  (因為 buckets 裡的 9 數量已經變 0)
------------------
8 沒有有在 buckets 裡
------------------
4 有在 buckets 裡
result = [9, 4, 4]
buckets = = {
    4: 0,
    9: 0,
    5: 1
}

Code

var intersect2 = function(nums1, nums2) {
    // like bucket sort 桶子排序， 因為要記什麼值有幾個所以用 obj
    let buckets = {};
    let result = []
    for(let i of nums1){
        // ex { 4這個值: 1次}
        buckets[i] = buckets[i] ? buckets[i] + 1 : 1;
    }
    for(let i of nums2){
        if(buckets[i]){
            buckets[i] --;
            result.push(i);
        }
    }

    return result;
};
console.log(intersect2([4,9,5, 4], [9,4,9,8,4]))

// faster than 85.07% of JavaScript online submissions