https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/
https://leetcode.com/problems/intersection-of-two-arrays-ii/
对其中一个数组建立哈希表,key为元素值,value为元素出现的个数。然后遍历另一个数组,查看表中有没有这个数,有则将该数加入结果中,并将value减一。
执行用时: c++ 4ms; java 7ms; python 48ms
c++
c++中哈希表不用判断key在不在里面,因为value初始化为0,直接对value每次++就行,比较简洁。
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int,int> mymap;
vector<int> res;
for(int i:nums1)
{
mymap[i]++;
}
for(int j:nums2)
{
if(--mymap[j]>=0) res.push_back(j);
}
return res;
}
};
java
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Map<Integer,Integer> map = new HashMap();
List<Integer> res = new ArrayList();
for(int i:nums1)
{
if (!map.containsKey(i)) map.put(i,1);
else map.put(i,map.get(i)+1);
}
for(int j:nums2)
{
if (map.containsKey(j))
{
res.add(j);
if (map.get(j)>1)
map.put(j,map.get(j)-1);
else map.remove(j);
}
}
//int[] res2 = (int[])res.toArray();
int[] res2 = new int[res.size()];
for(int i=0;i<res.size();i++)
res2[i] = res.get(i);
return res2;
}
}
python
class Solution:
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
dic1 = {}
for i in nums1:
if i in dic1:
dic1[i]+=1
else:
dic1[i]=1
res = []
for i in nums2:
if i in dic1:
if dic1[i]>1:
dic1[i]-=1
else:
dic1.pop(i)
res.append(i)
return res