【leetcode刷题】T44-两个数组的交集 II
【英文题目】（学习英语的同时，更能理解题意哟~）
Given two arrays, write a function to compute their intersection.
Example 1:
Input: nums1 = [,,,], nums2 = [,]
Output: [,]
Example 2:
Input: nums1 = [,,], nums2 = [,,,,]
Output: [,]
Note:
- Each element in the result should appear as many times as it shows in both arrays.
- The result can be in any order.
【中文题目】
给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [,,,], nums2 = [,]
输出: [,]
示例 2:
输入: nums1 = [,,], nums2 = [,,,,]
输出: [,]
说明：
- 输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
- 我们可以不考虑输出结果的顺序。
【思路】
使用字典/map 对所有元素进行计数，将共同元素存入结果中，重复次数为两个数组中该元素出现次数最小值。
【代码】
python版本
class Solution(object):
def get_dict(self, nums):
d = {}
for n in nums:
d[n] = d.get(n, ) +
return d
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
d1 = self.get_dict(nums1)
d2 = self.get_dict(nums2)
res = []
for k, v1 in d1.items():
if k in d2:
# 元素个数较小值
res.extend([k] * min(v1, d2[k]))
return res
C++版本
class Solution {
public:
map<int, int> get_map(vector<int>& num){
map<int, int> d;
for(int i=; i<num.size(); i++){
d[num[i]]++;
}
return d;
}
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
map<int, int> d1 = get_map(nums1);
map<int, int> d2 = get_map(nums2);
vector<int> res;
for(map<int, int>::iterator it=d1.begin(); it != d1.end(); it++){
if(d2.find(it->first) != d2.end()){
int times = min(it->second, d2[it->first]);
for(int j=; j<times; j++)
res.push_back(it->first);
}
}
return res;
}
};本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-04-19，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读