LeetCode 3164.优质数对的总数 II：哈希表+因式分解

【LetMeFly】3164.优质数对的总数 II：哈希表+因式分解

力扣题目链接：https://leetcode.cn/problems/find-the-number-of-good-pairs-ii/

给你两个整数数组 nums1 和 nums2，长度分别为 n 和 m。同时给你一个正整数 k。

如果 nums1[i] 可以被 nums2[j] * k 整除，则称数对 (i, j) 为 优质数对（0 <= i <= n - 1, 0 <= j <= m - 1）。

返回 优质数对 的总数。

示例 1：

输出：5

解释：

5个优质数对分别是 (0, 0), (1, 0), (1, 1), (2, 0), 和 (2, 2)。

示例 2：

输出：2

解释：

2个优质数对分别是 (3, 0) 和 (3, 1)。

提示：

• 1 <= n, m <= 105
• 1 <= nums1[i], nums2[j] <= 106
• 1 <= k <= 103

解题方法：哈希表+因式分解

遍历$nums1$数组，对于其中的元素$a$，求出$\lfloor \frac{a}{k}\rfloor$的所有因数并存入哈希表中。

遍历$nums2$数组，累加其中元素在哈希表中出现的次数即为答案。

如何求一个数$t$的所有因数？

用$i$从$1$到$\sqrt{t}$枚举，若$t$能整除$i$，则说明$i$和$\frac{\sqrt{t}}{i}$都是$t$的因数。

（这个过程有点类似“求一个数是否为质数”。）

• 时间复杂度$O(n\sqrt{\frac{M}{k}}+m)$，其中$M=\max (nums1)$
• 空间复杂度$O(\sqrt{\frac{M}{k}})$

AC代码

C++

typedef long long ll;
class Solution {
public:
    ll numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        ll ans = 0;
        unordered_map<int, int> ma;
        for (int t : nums1) {
            if (t % k) {
                continue;
            }
            t /= k;
            int sqrt_ = sqrt(t);
            for (int i = 1; i <= sqrt_; i++) {
                if (t % i == 0) {
                    ma[i]++;
                    ma[t / i]++;
                }
            }
            if (sqrt_ * sqrt_ == t) {
                ma[sqrt_]--;
            }
        }
        for (int t : nums2) {
            ans += ma[t];
        }
        return ans;
    }
};

Go

package main
import "math"

func numberOfPairs(nums1 []int, nums2 []int, k int) int64 {
    ma := map[int]int{}
    for _, t := range nums1 {
        if t % k != 0 {
            continue
        }
        t /= k
        sqrt_ := int(math.Sqrt(float64(t)));
        for i := 1; i <= sqrt_; i++ {
            if t % i == 0 {
                ma[i]++
                ma[t / i]++
            }
        }
        if sqrt_ * sqrt_ == t {
            ma[sqrt_]--
        }
    }
    ans := int64(0)
    for _, t := range nums2 {
        ans += int64(ma[t])
    }
    return ans
}

Java

import java.util.Map;
import java.util.HashMap;

class Solution {
    public long numberOfPairs(int[] nums1, int[] nums2, int k) {
        Map<Integer, Integer> ma = new HashMap<>();
        for (int t : nums1) {
            if (t % k != 0) {
                continue;
            }
            t /= k;
            int sqrt_ = (int)Math.sqrt(t);
            for (int i = 1; i <= sqrt_; i++) {
                if (t % i == 0) {
                    ma.merge(i, 1, Integer::sum);
                    ma.merge(t / i, 1, Integer::sum);
                }
            }
            if (sqrt_ * sqrt_ == t) {
                ma.merge(sqrt_, -1, Integer::sum);
            }
        }
        long ans = 0;
        for (int t : nums2) {
            ans += (long)ma.getOrDefault(t, 0);
        }
        return ans;
    }
}

Python

from typing import List
from collections import defaultdict
from math import sqrt

class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
        ma = defaultdict(int)
        for t in nums1:
            if t % k:
                continue
            t //= k
            sqrt_ = int(sqrt(t))
            for i in range(1, sqrt_ + 1):
                if t % i == 0:
                    ma[i] += 1
                    ma[t // i] += 1
            if sqrt_ * sqrt_ == t:
                ma[sqrt_] -= 1
        ans = 0
        for t in nums2:
            ans += ma[t]
        return ans

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/142865441