350. Intersection of Two Arrays II 两个数组的交集 II

@TOC

• Difficulty: Easy

# 题目描述

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

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.

• 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?

# 解题方法

# Java排序+双指针

``````public class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
ArrayList<Integer> arraylist = new ArrayList<Integer>();
//一定写上<Integer>，否则没法自动拆包装包
Arrays.sort(nums1);
Arrays.sort(nums2);
int index1 = 0;
int index2 = 0;
while (index1 < nums1.length && index2 < nums2.length) {
if (nums1[index1] == nums2[index2]) {
index1++;
index2++;
} else if (nums1[index1] < nums2[index2]) {
index1++;
} else {
index2++;
}
}
for (int i = 0; i < arraylist.size(); i++) {
}
}
}
``````

AC: 3 ms 超过96.76%

# Python排序+双指针

``````class Solution:
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
nums1.sort()
nums2.sort()
l1, l2 = 0, 0
N1, N2 = len(nums1), len(nums2)
res = []
while l1 != N1 and l2 != N2:
if nums1[l1] == nums2[l2]:
res.append(nums1[l1])
l1 += 1
l2 += 1
elif nums1[l1] < nums2[l2]:
l1 += 1
else:
l2 += 1
return res
``````

# Python解法使用字典

``````class Solution:
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
count1 = collections.Counter(nums1)
count2 = collections.Counter(nums2)
res = []
for k, v in count1.items():
if k in count2:
res += [k] * min(v, count2[k])
return res
``````

# 日期

2017 年 1 月 11 日 2018 年 11 月 6 日 —— 腰酸背痛要废了 2018 年 11 月 16 日 —— 又到周五了！