题目描述
给你两个整数数组 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 <= 501 <= nums1[i], nums2[j] <= 501 <= k <= 50
解法
方法一：暴力枚举
我们直接枚举所有的数位 $(x, y)$，判断是否满足 $x \bmod (y \times k) = 0$，如果满足则答案加一。
枚举结束后，返回答案即可。
时间复杂度 $O(m \times n)$，其中 $m$ 和 $n$ 分别是数组 $\textit{nums1}$ 和 $\textit{nums2}$ 的长度。空间复杂度 $O(1)$。
| class Solution:
def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
return sum(x % (y * k) == 0 for x in nums1 for y in nums2)
|
1
2
3
4
5
6
7
8
9
10
11
12
13 | class Solution {
public int numberOfPairs(int[] nums1, int[] nums2, int k) {
int ans = 0;
for (int x : nums1) {
for (int y : nums2) {
if (x % (y * k) == 0) {
++ans;
}
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | class Solution {
public:
int numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
int ans = 0;
for (int x : nums1) {
for (int y : nums2) {
if (x % (y * k) == 0) {
++ans;
}
}
}
return ans;
}
};
|
| func numberOfPairs(nums1 []int, nums2 []int, k int) (ans int) {
for _, x := range nums1 {
for _, y := range nums2 {
if x%(y*k) == 0 {
ans++
}
}
}
return
}
|
| function numberOfPairs(nums1: number[], nums2: number[], k: number): number {
let ans = 0;
for (const x of nums1) {
for (const y of nums2) {
if (x % (y * k) === 0) {
++ans;
}
}
}
return ans;
}
|
方法二：哈希表 + 枚举倍数
我们用一个哈希表 $\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 int 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);
}
int 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 += 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:
int 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);
}
int ans = 0;
for (auto& [x, v] : cnt2) {
int 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 int) {
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 += s * 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;
}
|