【调和级数】100321. 优质数对的总数 II

本文涉及知识点

调和级数
质数、最大公约数、菲蜀定理

LeetCode100321. 优质数对的总数 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 <= 10⁵
1 <= nums1[i], nums2[j] <= 10⁶
1 <= k <= 10³

调和级数

nums1中的元素如果不是k的倍数，删除。是k的倍数， /= k。
cnt1 记录nums1中各元素的数量。
令 max1 = (nums1)
$\forall$ n $\in$ nums2。如果n的m倍(m>0) 在nums1中存在，则是优质对。
如果n $\times$ m > max，则无需继续枚举m。
枚举1到y的不超过y的倍数，时间复杂度：y + y/2+y/3 $\cdots$ 1 就是调和级数，故时间复杂度是：O(ylogy)。
注意：如果nums2有重复元素，则时间复杂度是O(nn)。比如：全部是1。所以：必须用cnt2记录nums2各元素数量。

超时代码

class Solution {
public:
	long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
		int iMax = *std::max_element(nums1.begin(), nums1.end());
		vector<int> vCnt1(iMax + 1);
		for (const auto& n : nums1) {
			if (0 != n % k) {continue;}
			vCnt1[n / k]++;
		}
		while (vCnt1.size() &&(vCnt1.back() == 0)) {
			vCnt1.pop_back();
		}
		iMax = vCnt1.size() - 1;
		long long llRet = 0;
		for (const auto& n : nums2) {
			for (int tmp = n; tmp <= iMax; tmp += n) {
				llRet += vCnt1[tmp];
			}
		}
		return llRet;
	}
};

代码

class Solution {
public:
	long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
		vector<int> tmp;
		for (const auto& n : nums1) {
			if (0 != n % k) { continue; }
			tmp.emplace_back(n/k);
		}
		if (tmp.empty()) { return 0; }
		int iMax = *std::max_element(tmp.begin(), tmp.end());
		vector<int> vCnt1(iMax + 1);
		for (auto& n : tmp) {
			vCnt1[n]++;
		}
		const int iMax2 = *std::max_element(nums2.begin(), nums2.end());
		vector<long long> vCnt2(iMax2+1);
		for (auto& n : nums2) {
			vCnt2[n]++;
		}
		long long llRet = 0;
		for (int i = 1; i <= iMax2; i++ ) {
			for (int tmp = i; tmp <= iMax; tmp += i) {
				llRet += vCnt1[tmp]*vCnt2[i];
			}
		}
		return llRet;
	}
};

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛