【英文题目】(学习英语的同时,更能理解题意哟~)
Given two arrays, write a function to compute their intersection.
Example 1:
Input: nums1 = [,,,], nums2 = [,]
Output: [,]
Example 2:
Input: nums1 = [,,], nums2 = [,,,,]
Output: [,]
Note:
【中文题目】
给定两个数组,编写一个函数来计算它们的交集。
示例 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;
}
};