跳转至

3164. 优质数对的总数 II

题目描述

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

解法

方法一：哈希表 + 枚举倍数

我们用一个哈希表 \(\textit{cnt1}\) 记录数组 \(\textit{nums1}\) 中每个数除以 \(k\) 的商的出现次数，用一个哈希表 \(\textit{cnt2}\) 记录数组 \(\textit{nums2}\) 中每个数的出现次数。

接下来，我们枚举数组 \(\textit{nums2}\) 中的每个数 \(x\)，对于每个数 \(x\)，我们枚举 \(x\) 的倍数 \(y\)，其中 \(y\) 的范围是 \([x, \textit{mx}]\)，其中 \(\textit{mx}\) 是 \(\textit{cnt1}\) 中的最大键值，然后我们统计 \(\textit{cnt1}[y]\) 的和，记为 \(s\)，最后我们将 \(s \times v\) 累加到答案中，其中 \(v\) 是 \(\textit{cnt2}[x]\)。

时间复杂度 \(O(n + m + (M / k) \times \log m)\)，空间复杂度 \(O(n + m)\)，其中 \(n\) 和 \(m\) 分别是数组 \(\textit{nums1}\) 和 \(\textit{nums2}\) 的长度，而 \(M\) 是数组 \(\textit{nums1}\) 中的最大值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
        cnt1 = Counter(x // k for x in nums1 if x % k == 0)
        if not cnt1:
            return 0
        cnt2 = Counter(nums2)
        ans = 0
        mx = max(cnt1)
        for x, v in cnt2.items():
            s = sum(cnt1[y] for y in range(x, mx + 1, x))
            ans += s * v
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public long numberOfPairs(int[] nums1, int[] nums2, int k) {
        Map<Integer, Integer> cnt1 = new HashMap<>();
        for (int x : nums1) {
            if (x % k == 0) {
                cnt1.merge(x / k, 1, Integer::sum);
            }
        }
        if (cnt1.isEmpty()) {
            return 0;
        }
        Map<Integer, Integer> cnt2 = new HashMap<>();
        for (int x : nums2) {
            cnt2.merge(x, 1, Integer::sum);
        }
        long ans = 0;
        int mx = Collections.max(cnt1.keySet());
        for (var e : cnt2.entrySet()) {
            int x = e.getKey(), v = e.getValue();
            int s = 0;
            for (int y = x; y <= mx; y += x) {
                s += cnt1.getOrDefault(y, 0);
            }
            ans += 1L * s * v;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        unordered_map<int, int> cnt1;
        for (int x : nums1) {
            if (x % k == 0) {
                cnt1[x / k]++;
            }
        }
        if (cnt1.empty()) {
            return 0;
        }
        unordered_map<int, int> cnt2;
        for (int x : nums2) {
            ++cnt2[x];
        }
        int mx = 0;
        for (auto& [x, _] : cnt1) {
            mx = max(mx, x);
        }
        long long ans = 0;
        for (auto& [x, v] : cnt2) {
            long long s = 0;
            for (int y = x; y <= mx; y += x) {
                s += cnt1[y];
            }
            ans += s * v;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func numberOfPairs(nums1 []int, nums2 []int, k int) (ans int64) {
    cnt1 := map[int]int{}
    for _, x := range nums1 {
        if x%k == 0 {
            cnt1[x/k]++
        }
    }
    if len(cnt1) == 0 {
        return 0
    }
    cnt2 := map[int]int{}
    for _, x := range nums2 {
        cnt2[x]++
    }
    mx := 0
    for x := range cnt1 {
        mx = max(mx, x)
    }
    for x, v := range cnt2 {
        s := 0
        for y := x; y <= mx; y += x {
            s += cnt1[y]
        }
        ans += int64(s) * int64(v)
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function numberOfPairs(nums1: number[], nums2: number[], k: number): number {
    const cnt1: Map<number, number> = new Map();
    for (const x of nums1) {
        if (x % k === 0) {
            cnt1.set((x / k) | 0, (cnt1.get((x / k) | 0) || 0) + 1);
        }
    }
    if (cnt1.size === 0) {
        return 0;
    }
    const cnt2: Map<number, number> = new Map();
    for (const x of nums2) {
        cnt2.set(x, (cnt2.get(x) || 0) + 1);
    }
    const mx = Math.max(...cnt1.keys());
    let ans = 0;
    for (const [x, v] of cnt2) {
        let s = 0;
        for (let y = x; y <= mx; y += x) {
            s += cnt1.get(y) || 0;
        }
        ans += s * v;
    }
    return ans;
}

评论