class Solution {
public:
long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
}
};
100321. 优质数对的总数 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 <= 1051 <= nums1[i], nums2[j] <= 1061 <= k <= 103原站题解
rust 解法, 执行用时: 71 ms, 内存消耗: 5.3 MB, 提交时间: 2024-10-11 09:22:46
use std::collections::HashMap;
impl Solution {
pub fn number_of_pairs(nums1: Vec<i32>, nums2: Vec<i32>, k: i32) -> i64 {
let mut cnt1 = HashMap::new();
for x in nums1 {
if x % k == 0 {
*cnt1.entry(x / k).or_insert(0) += 1;
}
}
if cnt1.is_empty() {
return 0;
}
let mut cnt2 = HashMap::new();
for x in nums2 {
*cnt2.entry(x).or_insert(0) += 1;
}
let mut ans = 0i64;
let u = *cnt1.keys().max().unwrap();
for (x, cnt) in cnt2 {
let mut s = 0;
for y in (x..=u).step_by(x as usize) { // 枚举 x 的倍数
if let Some(&c) = cnt1.get(&y) {
s += c;
}
}
ans += s as i64 * cnt as i64;
}
ans
}
// 枚举因子
pub fn number_of_pairs2(nums1: Vec<i32>, nums2: Vec<i32>, k: i32) -> i64 {
let mut cnt = HashMap::new();
for mut x in nums1 {
if x % k != 0 {
continue;
}
x /= k;
let mut d = 1;
while d * d <= x {
if x % d == 0 {
*cnt.entry(d).or_insert(0) += 1;
if d * d < x {
*cnt.entry(x / d).or_insert(0) += 1;
}
}
d += 1;
}
}
nums2.iter().map(|x| *cnt.get(x).unwrap_or(&0) as i64).sum()
}
}
javascript 解法, 执行用时: 717 ms, 内存消耗: 84.3 MB, 提交时间: 2024-10-11 09:22:12
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @param {number} k
* @return {number}
*/
var numberOfPairs = function(nums1, nums2, k) {
const cnt = new Map();
for (let x of nums1) {
if (x % k) {
continue;
}
x /= k;
for (let d = 1; d * d <= x; d++) { // 枚举因子
if (x % d) {
continue;
}
cnt.set(d, (cnt.get(d) || 0) + 1); // 统计因子
if (d * d < x) {
cnt.set(x / d, (cnt.get(x / d) ?? 0) + 1); // 因子总是成对出现
}
}
}
let ans = 0;
for (const x of nums2) {
ans += cnt.get(x) ?? 0;
}
return ans;
};
// 枚举倍数
const numberOfPairs2 = function(nums1, nums2, k) {
const cnt1 = new Map();
let u = 0;
for (const x of nums1) {
if (x % k === 0) {
u = Math.max(u, x / k);
cnt1.set(x / k, (cnt1.get(x / k) ?? 0) + 1);
}
}
if (u === 0) {
return 0;
}
const cnt2 = new Map();
for (const x of nums2) {
cnt2.set(x, (cnt2.get(x) ?? 0) + 1);
}
let ans = 0;
for (const [x, cnt] of cnt2.entries()) {
let s = 0;
for (let y = x; y <= u; y += x) { // 枚举 x 的倍数
s += cnt1.get(y) ?? 0;
}
ans += s * cnt;
}
return ans;
}
python3 解法, 执行用时: 545 ms, 内存消耗: 41.5 MB, 提交时间: 2024-05-26 19:00:53
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
ans = 0
u = max(cnt1)
for i, c in Counter(nums2).items():
s = sum(cnt1[j] for j in range(i, u + 1, i))
ans += s * c
return ans
# 统计因子
def numberOfPairs2(self, nums1: List[int], nums2: List[int], k: int) -> int:
cnt = defaultdict(int)
for x in nums1:
if x % k:
continue
x //= k
for d in range(1, isqrt(x) + 1):
if x % d:
continue
cnt[d] += 1
if d * d < x:
cnt[x // d] += 1
return sum(cnt[x] for x in nums2)
golang 解法, 执行用时: 663 ms, 内存消耗: 21.5 MB, 提交时间: 2024-05-26 18:59:14
func numberOfPairs(nums1, nums2 []int, k int) (ans int64) {
cnt := map[int]int{}
for _, x := range nums1 {
if x%k > 0 {
continue
}
x /= k
for d := 1; d*d <= x; d++ {
if x%d == 0 {
cnt[d]++
if d*d < x {
cnt[x/d]++
}
}
}
}
for _, x := range nums2 {
ans += int64(cnt[x])
}
return
}
func numberOfPairs2(nums1, nums2 []int, k int) (ans int64) {
cnt1 := map[int]int{}
for _, x := range nums1 {
if x%k == 0 {
cnt1[x/k]++
}
}
cnt2 := map[int]int{}
for _, x := range nums2 {
cnt2[x]++
}
m := slices.Max(nums1) / k
for i, c := range cnt2 {
s := 0
for j := i; j <= m; j += i {
s += cnt1[j]
}
ans += int64(s * c)
}
return
}
cpp 解法, 执行用时: 293 ms, 内存消耗: 165.1 MB, 提交时间: 2024-05-26 18:56:30
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]++;
}
long long ans = 0;
int u = ranges::max_element(cnt1)->first;
for (auto& [i, c] : cnt2) {
int s = 0;
for (int j = i; j <= u; j += i) {
s += cnt1.contains(j) ? cnt1[j] : 0;
}
ans += (long long) s * c;
}
return ans;
}
// 统计因子
long long numberOfPairs2(vector<int>& nums1, vector<int>& nums2, int k) {
unordered_map<int, int> cnt;
for (int x : nums1) {
if (x % k) {
continue;
}
x /= k;
for (int d = 1; d * d <= x; d++) {
if (x % d) {
continue;
}
cnt[d]++;
if (d * d < x) {
cnt[x / d]++;
}
}
}
long long ans = 0;
for (int x : nums2) {
ans += cnt.contains(x) ? cnt[x] : 0;
}
return ans;
}
};
java 解法, 执行用时: 505 ms, 内存消耗: 57 MB, 提交时间: 2024-05-26 18:54:22
class Solution {
// 统计因子
public long numberOfPairs(int[] nums1, int[] nums2, int k) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int x : nums1) {
if (x % k != 0) {
continue;
}
x /= k;
for (int d = 1; d * d <= x; d++) {
if (x % d > 0) {
continue;
}
cnt.merge(d, 1, Integer::sum);
if (d * d < x) {
cnt.merge(x / d, 1, Integer::sum);
}
}
}
long ans = 0;
for (int x : nums2) {
ans += cnt.getOrDefault(x, 0);
}
return ans;
}
// 枚举倍数
public long numberOfPairs2(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 u = Collections.max(cnt1.keySet());
for (Map.Entry<Integer, Integer> e : cnt2.entrySet()) {
int s = 0;
int i = e.getKey();
for (int j = i; j <= u; j += i) {
if (cnt1.containsKey(j)) {
s += cnt1.get(j);
}
}
ans += (long) s * e.getValue();
}
return ans;
}
}