日期: 2024年10月10日

目标

给你两个整数数组 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 <= 50
• 1 <= nums1[i], nums2[j] <= 50
• 1 <= k <= 50

思路

有两个数组 nums1 nums2，计算满足 nums1[i] % (nums2[j] * k) == 0 的数对 (i, j) 的个数。

数据量不大直接枚举即可。可以优化的点是提前判断 nums[i] 能否整除 k，如果不能，则必然也无法整除 nums2[j] * k，省去了内部循环乘以 k 的计算。

官网题解的非暴力做法是使用两个哈希表 map1 map2 分别统计 nums1 nums2 中元素出现的次数，同时找出 nums1 中的最大值 max1，然后枚举 map2 的 keyset，内层循环初值与步长为 nums2[j] * k，判断倍数是否在 map1 中，直到 倍数 <= max1。这样做的好处是寻找数对的时间复杂度由原来的 O(mn) 变成了 O(n + m + max1/k * log(m))。

这里的 log(max2) 是一个近似的估计，针对每一个外层循环的值 a，内层循环的次数为 max1 / (a * k)，假设 nums2 的元素值为 1 2 …… max2，那么总的循环次数为 (max1/k)Σ(1/a) 这是调和级数的形式，即 1 + 1/2 + 1/3 + …… + 1/max2 + ……，调和级数的部分和 Hn 近似为 ln(max2)，这里 max2 其实是 nums2 的个数 m。当 nums2 中的元素都是 1 时，map2.keySet 中的元素个数也为 1，进化为 O(n + m + max1/k)，当 nums2 中的元素都是 max2 时，进化为 O(n + m + max1/(max2 * k))。

代码

/**
 * @date 2024-10-10 8:56
 */
public class NumberOfPairs3162 {

    public int numberOfPairs_v1(int[] nums1, int[] nums2, int k) {
        int res = 0;
        for (int i = 0; i < nums1.length; i++) {
            if (nums1[i] % k != 0) {
                continue;
            }
            int tmp = nums1[i] / k;
            for (int j = 0; j < nums2.length; j++) {
                if (tmp % nums2[j] == 0) {
                    res++;
                }
            }
        }
        return res;
    }

    public int numberOfPairs(int[] nums1, int[] nums2, int k) {
        int res = 0;
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                if (nums1[i] % (nums2[j] * k) == 0){
                    res++;
                }
            }
        }
        return res;
    }

}

性能