## 题目描述：

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.

• What if the given array is already sorted? How would you optimize your algorithm?
• What if nums1's size is small compared to num2'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的长度＜nums2的长度？哪一种算法更好？
• 如果nums2的元素存储在磁盘上，并且内存大小有限，不足以将其一次性的加载到内存中。此时应当怎样做？

## Python代码：

``````class Solution(object):
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
nums1, nums2 = sorted(nums1), sorted(nums2)
p1 = p2 = 0
ans = []
while p1 < len(nums1) and p2 < len(nums2):
if nums1[p1] < nums2[p2]:
p1 += 1
elif nums1[p1] > nums2[p2]:
p2 += 1
else:
ans += nums1[p1],
p1 += 1
p2 += 1
return ans
``````

## Python代码：

``````class Solution(object):
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
c = collections.Counter(nums1)
ans = []
for x in nums2:
if c[x] > 0:
ans += x,
c[x] -= 1
return ans
``````

Pingbacks已关闭。