Intersection of Two Arrays II
Given two arrays, write a function to compute their intersection.
Example 1:
1 | Input: nums1 = [1,2,2,1], nums2 = [2,2] |
Example 2:
1 | Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] |
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?
题意分析
寻找两个数组的交集,并以尽可能多的次数出现。首先考虑遍历其中一个数组,将各数字出现的次数保存在map中,然后对另外一个数组做遍历,若map含有这个key就加入到结果list中,并且该key对应的value值要减小1,若减小至0,则删除这个key。最后将list转为数组即可。
代码实现
1 | class Solution { |