题目描述
给你两个整数数组 nums1 和 nums2,长度分别为 n 和 m。同时给你一个正整数 k。
如果 nums1[i] 可以被 nums2[j] * k 整除,则称数对 (i, j) 为 优质数对(0 <= i <= n - 1, 0 <= j <= m - 1)。
返回 优质数对 的总数。
思路
-
nums1[i]可以被nums2[j] * k整除,那么nums2[j] * k是nums[i]的因子,通过map<int,int>统计nums1所有元素各个因子的总数.
例如[12,15],12的因子有1、12、2、6、3、4,15的因子有1、15、3、5,那么map[1] = 2,map[3] = 2,map[12] = 1·····
-
那么能整除nums2[j] * k的元素数量就是map[nums2[j] * k]
-
如果map[i]不能整除k,那么也就不能整除nums2[j] * k,可以直接略过。
代码
class Solution {
public:
long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
long long result = 0;
unordered_map<int,int> map;
for (int i = 0; i < nums1.size();i++) {
if (nums1[i] % k != 0) continue;
for (int j = 1; j * j <= nums1[i]; j++) {
if (nums1[i] % j == 0) {
map[j]++;
if(nums1[i] / j != j) map[nums1[i] / j]++;
}
}
}
for (int i = 0; i < nums2.size(); i++) {
int knums2 = nums2[i] * k;
result += map[knums2];
}
return result;
}
};
标签:map,数对,long,II,100321,整除,nums1,nums2
From: https://www.cnblogs.com/EavenWang/p/18214058