LeetCode 350. Intersection of Two Arrays II(两个数组的交集 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.
解法一
思路
这题和之前的LeetCode 349. Intersection of Two Arrays(两个数组的交集)唯一区别就是,将相同的数组元素当作不同的个体来看,而非合并为同一元素。例如[1, 2, 2, 3]
和[2, 2, 2]
的交集是[2, 2]
。
那么相对于LeetCode 349. Intersection of Two Arrays(两个数组的交集),这题解法上也只需要将之前的Set替换为Map:
- 遍历第一个数组时,在记录key的同时也记录元素出现次数
遍历第二个数组时,对于每个元素
如果其出现在Map中,则查看Map的value
- 如果value为0,则代表此元素为第二个数组中多出现的,忽略。
- 如果value不为0,则代表此元素在第一个数组中也出现了,输出到结果,并将此value减1。
- 如果其未出现在Map中,则代表此元素未在第一个数组中出现,忽略。
Python
class Solution:
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
nums1_dict = {}
for num in nums1:
nums1_dict[num] = nums1_dict.get(num, 0) + 1
result = []
for num in nums2:
if num in nums1_dict and nums1_dict[num] != 0:
result.append(num)
nums1_dict[num] -= 1
return result
Java
public class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Map<Integer, Integer> nums1Map = new HashMap<>();
for (int num : nums1) {
nums1Map.put(num, nums1Map.getOrDefault(num, 0) + 1);
}
List<Integer> result = new ArrayList<>();
for (int num : nums2) {
if (nums1Map.containsKey(num) && nums1Map.get(num) != 0) {
result.add(num);
nums1Map.put(num, nums1Map.get(num) - 1);
}
}
int[] resultArray = new int[result.size()];
int index = 0;
for (int item : result) {
resultArray[index++] = item;
}
return resultArray;
}
}
C++
class Solution {
public:
vector<int> intersect(vector<int> &nums1, vector<int> &nums2) {
map<int, int> nums1Map;
for (int num : nums1) {
nums1Map[num]++;
}
vector<int> resultVector;
for (int num : nums2) {
if (nums1Map.find(num) != nums1Map.end() && nums1Map[num] != 0) {
resultVector.push_back(num);
nums1Map[num]--;
}
}
return resultVector;
}
};