日期: 2024 年 10 月 11 日

目标

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

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

返回 优质数对 的总数。

示例 1：

输入：nums1 = [1,3,4], nums2 = [1,3,4], k = 1
输出：5
解释：
5个优质数对分别是 (0, 0), (1, 0), (1, 1), (2, 0), 和 (2, 2)。

示例 2：

输入：nums1 = [1,2,4,12], nums2 = [2,4], k = 3
输出：2
解释：
2个优质数对分别是 (3, 0) 和 (3, 1)。

说明：

• 1 <= n, m <= 10^5
• 1 <= nums1[i], nums2[j] <= 10^6
• 1 <= k <= 10^3

思路

这与昨天 3162.优质数对的总数I 的区别是数据范围变大了，暴力解法不可行。

枚举因子的时间复杂度为 O(n * sqrt(max1/k) + m)， 代入计算 10^5 * 10^3 + 10^5 大约 10^8，耗时560ms。

枚举倍数的时间复杂度为 O(n + m + max1/k * log(m))，10^5 + 10^5 + 10^6 * ln(10^5) ≈ 10^5 + 10^5 + 10^6 * 11.51，10^7，耗时 88ms。

代码

/**
 * @date 2024-10-11 8:40
 */
public class NumberOfPairs3164 {

    /**
     * 枚举因子 560ms
     */
    public long numberOfPairs_v1(int[] nums1, int[] nums2, int k) {
        Map<Integer, Integer> factorCnt = new HashMap<>();
        for (int num : nums1) {
            if (num % k != 0) {
                continue;
            }
            num /= k;
            for (int i = 1; i * i <= num; i++) {
                if (num % i != 0) {
                    continue;
                }
                factorCnt.merge(i, 1, Integer::sum);
                if (i * i < num) {
                    factorCnt.merge(num / i, 1, Integer::sum);
                }
            }
        }
        long res = 0L;
        for (int num : nums2) {
            res += factorCnt.getOrDefault(num, 0);
        }
        return res;
    }

    /**
     * 枚举倍数 88ms
     */
    public long numberOfPairs(int[] nums1, int[] nums2, int k) {
        Map<Integer, Integer> map1 = new HashMap<>(nums1.length);
        Map<Integer, Integer> map2 = new HashMap<>(nums2.length);
        int max1 = 0;
        for (int num : nums1) {
            map1.merge(num, 1, Integer::sum);
            max1 = Math.max(max1, num);
        }
        for (int num : nums2) {
            map2.merge(num, 1, Integer::sum);
        }
        long res = 0L;
        for (int num : map2.keySet()) {
            int multiple = num * k;
            for (int i = multiple; i <= max1; i += multiple) {
                if (map1.containsKey(i)) {
                    res += (long) map1.get(i) * map2.get(num);
                }
            }
        }
        return res;
    }

}

性能