两个数组的交集 II
仅记录一下刷题过程中的思路
哈希表/字典
自己的想法
- 给集合中的数据进行排序(不排序也行);
- 用两个哈希表记录集合中每个数字出现的次数;
- 创建第三个哈希表,记录两个哈希表中重复的数字;
- 因为键是独一无二、不重复的,在键相等的情况下:
(1)如果值相等,说明键的个数在集合中出现的次数是一样的;
(2)如果值不相等,说明键的个数不一样,那么就取最小的个数;
具体代码
class Solution(object):
def intersect(self, nums1, nums2):
# 给 nums1 计数
dict1 = {}
nums1.sort()
for n1 in nums1:
if n1 not in dict1:
dict1[n1] = 1
else:
tempt = dict1[n1]
dict1[n1] = tempt+1
# 给 nums2 计数
dict2 = {}
nums2.sort()
for n2 in nums2:
if n2 not in dict2:
dict2[n2] = 1
else:
tempt =dict2[n2]
dict2[n2] = tempt + 1
# 进行比较
dict3 = {}
for i in dict1:
if i in dict2:
if dict1[i] == dict2[i]:
tempt = dict1[i]
dict3[i] = tempt
else:
tempt = min(dict1[i],dict2[i])
dict3[i] = tempt
rel = []
for v in dict3:
for j in range(dict3[v]):
rel.append(v)
return rel