百度推广做网站,各地微信推广平台大全,网站建设原型图,centos wordpress 空白本文涉及知识点
调和级数 质数、最大公约数、菲蜀定理
LeetCode100321. 优质数对的总数 II
给你两个整数数组 nums1 和 nums2#xff0c;长度分别为 n 和 m。同时给你一个正整数 k。 如果 nums1[i] 可以被 nums2[j] * k 整除#xff0c;则称数对 (i, j) 为 优质数对#…本文涉及知识点
调和级数 质数、最大公约数、菲蜀定理
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 105 1 nums1[i], nums2[j] 106 1 k 103
调和级数
nums1中的元素如果不是k的倍数删除。是k的倍数 / k。 cnt1 记录nums1中各元素的数量。 令 max1 (nums1) ∀ \forall ∀n ∈ \in ∈nums2。 如果n的m倍(m0) 在nums1中存在则是优质对。 如果n × \times ×m max则无需继续枚举m。 枚举1到y的不超过y的倍数时间复杂度y y/2y/3 ⋯ \cdots ⋯ 1 就是调和级数故时间复杂度是O(ylogy)。 注意如果nums2有重复元素则时间复杂度是O(nn)。比如全部是1。所以必须用cnt2记录nums2各元素数量。
超时代码
class Solution {
public:long long numberOfPairs(vectorint nums1, vectorint nums2, int k) {int iMax *std::max_element(nums1.begin(), nums1.end());vectorint 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(vectorint nums1, vectorint nums2, int k) {vectorint 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());vectorint vCnt1(iMax 1);for (auto n : tmp) {vCnt1[n];}const int iMax2 *std::max_element(nums2.begin(), nums2.end());vectorlong long vCnt2(iMax21);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
相关下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话《喜缺全书算法册》以原理、正确性证明、总结为主。闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
