leetcode:350.两个数组的交集 II

两个数组的交集 II
仅记录一下刷题过程中的思路

哈希表/字典

自己的想法

  1. 给集合中的数据进行排序(不排序也行);
  2. 用两个哈希表记录集合中每个数字出现的次数;
  3. 创建第三个哈希表,记录两个哈希表中重复的数字;
  4. 因为键是独一无二、不重复的,在键相等的情况下:
    (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

待续补充……

上一篇:牛客——等价串


下一篇:Java路线学习与日语n2准备的粗略计划表