350. Intersection of Two Arrays II
Description
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?
Solution
/**
* Solved with hash table
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersect = function(nums1, nums2) {
"use strict";
let table = {};
let large = null, small = null;
if (nums1.length > nums2.length) {
large = nums1;
small = nums2;
} else {
large = nums2;
small = nums1;
}
for (let i = 0; i < large.length; i++) {
if (table[large[i]] === undefined) {
table[large[i]] = 0;
}
table[large[i]]++;
}
let result = [];
for (let i = 0; i < small.length; i++) {
if (table[small[i]]) {
table[small[i]]--;
result.push(small[i]);
}
}
return result;
};