LeetCode 350. Intersection of Two Arrays II

題目

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

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

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?

翻譯

尋找兩個陣列的交集。

範例：
nums1 = [1, 2, 2, 1]，nums2 = [2, 2]， return [2,2]

注意：

• 同樣的數字在回傳的陣列中可重複出現
• 回傳的陣列可以不管裡面的數字排序

進階：

• 如果陣列已經排序過，如何最佳化演算法?
• 如果nums1長度小於nums2長度，如何最佳化演算法?
• 如果nums2儲存在光碟上，所以無法一次讀盡所有的元素，要怎麼處理?　

思路

不管進階的部分，這題跟LeetCode 349. Intersection of Two Arrays很像，只是交集的數字可重複出現。

先找出哪個陣列較長為store，較短的為ary，ary[i]如果可以在store中找到值，表示這是交集的數字，將這數字放入回傳陣列，移除store中第一個交集數字。

解題

    var store, array;
    var number = [];
    if(nums1.length > nums2.length){
        store = nums1;
        array = nums2;
    } else {
        store = nums2;
        array = nums1;       
    }

    for(var i = 0; i < array.length ; i++){
        var v = array[i];
        if(store.indexOf(v) >= 0){
            store[store.indexOf(v)] = null;
            number.push(v);
        }
    }  
    return number;