3164.优质数对||：

题目：

给你两个整数数组 nums1 和 nums2，长度分别为 n 和 m。同时给你一个正整数 k。
如果 nums1[i] 可以被 nums2[j] * k 整除，则称数对 (i, j) 为优质数对（0 <= i <= n - 1, 0 <= j <= m - 1）。
返回优质数对的总数。

个人总结

1.本题之前有优质数对|，可以使用O(n^2)的遍历进行解决。本题使用哈希表进行优化，主要优化的部分为“nums1和nums2中有很多重复元素时，使用哈希表只需要将元素出现的次数乘起来就可以了”
2.判断元素是否在哈希表，时间复杂度高的话，不采用遍历，可以使用跨越式的枚举

# 下面是取值b*k的倍数，然后判断是否在nums1的哈希表count1中，而不是下面错误的在count1中遍历元素看是否有是b*k倍数的
for a in range(b*k,max1+1,b*k):
    if a in count1:
    # 更新结果（用a的次数乘b的次数）——哈希表
        res+=count1[a]*cnt

# 下面是时间复杂度高的没有枚举的方法,在count1中遍历元素看是否有是b*k倍数的
for a,cnt1 in count1.items():
    if a % b==0:
        res+=cnt1*cnt2

Counter()

3.学习到了collections模块的Counter()方法，可以支持方便、快速的计数，将元素数量统计，然后计数并返回一个字典，键为元素，值为元素个数。

用法

from collections import Counter

list1 = ["a", "a", "a", "b", "c", "c", "f", "g", "g", "g", "f"]
dic = Counter(list1)
print(dic)
#结果:次数是从高到低的
#Counter({'a': 3, 'g': 3, 'c': 2, 'f': 2, 'b': 1})

print(dict(dic))
#结果:按字母顺序排序的
#{'a': 3, 'b': 1, 'c': 2, 'f': 2, 'g': 3}

print(dic.items()) #dic.items()获取字典的key和value
#结果:按字母顺序排序的
#dict_items([('a', 3), ('b', 1), ('c', 2), ('f', 2), ('g', 3)])

print(dic.keys())
#结果:
#dict_keys(['a', 'b', 'c', 'f', 'g'])

print(dic.values())
#结果：
#dict_values([3, 1, 2, 2, 3])

print(sorted(dic.items(), key=lambda s: (-s[1])))
#结果:按统计次数降序排序
#[('a', 3), ('g', 3), ('c', 2), ('f', 2), ('b', 1)]

for i, v in dic.items():
    if v == 1:
        print(i)
#结果:
#b

下面两个方法等价：

1
2
3

counter = defaultdict(int)
for num in nums:
    counter[num]+=1

1	counter = Counter(nums)

BTW,使用for num in nums在数组中进行迭代进行的操作不会对原数组元素进行修改，要想修改的话需使用for i in range(0,len(nums))

代码：

def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
        # count为Counter({'a': 3, 'g': 3, 'c': 2, 'f': 2, 'b': 1})
        # 采用方法为枚举nums2元素的倍数
        # 对nums1中出现元素进行计数
        count1=Counter(nums1)
        max1=max(count1)
        res=0
        # 对items()进行遍历nums2出现过的数b
        for b,cnt in Counter(nums2).items():
            # 枚举b×k的倍数，如果在nums1出现过就可以组成优质数对，更新结果（用a的次数乘b的次数）。
            # 下面是取值b*k的倍数，然后判断是否在nums1的哈希表count1中，而不是下面错误的在count1中遍历元素看是否有是b*k倍数的
            for a in range(b*k,max1+1,b*k):
                if a in count1:
                # 更新结果（用a的次数乘b的次数）——哈希表
                    res+=count1[a]*cnt
        return res         
# 下面使用哈希表+遍历导致时间复杂度不通过
        # res=0
        # count1=defaultdict(int)
        # count2=defaultdict(int)
        
        # for num in nums1:
        #     count1[num]+=1
        # for num in nums2:
        #     count2[num]+=1
        # max(count1)+1不要放在之后的循环中，要先将max赋值给max1，避免了循环中重复计算
        # max1 = max(count1)+1
        # # 可以使用Counter简化
        # # count1 = Counter(nums1)
        # # count2 = Counter(nums2)
        ## 没有枚举nums2中元素的倍数，导致时间复杂度高        
        # for b,cnt2 in count2.items():
        ## 应该修改下面的for循环，枚举nums2*k的倍数，如果在nums1中出现过就可以组成优质数对
        #     for a in range(b*k,max1,b*k):
        #     if a in count1:
        #         res+=count1[a]*cnt2
        ## 下面是时间复杂度高的没有枚举的方法
        ##     for a,cnt1 in count1.items():
        ##         if a % (b*k)==0:
        ##             res+=cnt1*cnt2
        # return res

数据结构与算法总结

3164.优质数对||：

题目：

标签：

个人总结

Counter()

用法

代码：