LeetCode 1819. 序列中不同最大公约数的数目(数论)
题目描述
给你一个由正整数组成的数组
nums
。数字序列的 最大公约数 定义为序列中所有整数的共有约数中的最大整数。
例如,序列
[4,6,16]
的最大公约数是2
。
数组的一个 子序列 本质是一个序列,可以通过删除数组中的某些元素(或者不删除)得到。例如,
[2,5,10]
是[1,2,1,2,4,1,5,10]
的一个子序列。
计算并返回nums
的所有 非空 子序列中 不同 最大公约数的 数目 。来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/number-of-different-subsequences-gcds
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题目分析
看到 GCD(最大公约数)的题目我就头大,因为我除了质因数分解就啥都不知道了。
这题看起来不算难,但是我思考了很久还是没能独立做出来,最后还是翻阅了力扣讨论区。
我开始想的是 DP 或者排序,又试了下暴力破解(毫无疑问超时)。后面看到数据范围也不是很大,在思考枚举每个数是否能够成功答案,但是没有能够继续思考下去。。。如何判断该数字是否能够成为某些数字的 GCD 呢?
(虽然题目要求是子序列,但其实顺序并不重要,下面我就直接说子集)
假设要计算数字 x
是否能成为某个子集的 GCD ,首先要找出在数组中,能够成为 x
的倍数的数字集合(显然,不能整除 x
的数字,约数不可能有 x
)。然后求出这个集合的 GCD 假设为 gcd(x倍数集合)
,如果 gcd(x倍数集合)
等于 x
证明这些数字的就是一个满足 GCD 为 x
的子集。
不会证明,但结论还是比较直观的 =。=
由于 \(\sum_{i=1}^n \frac{n}{i} = n*\sum_{i=1}^n \frac{1}{i} = O(n*logn)\)
求 gcd 均摊是 \(O(m*logm)\) 的, 故该算法的复杂度也为 \(O(m*logm) + O(m*logm)=O(m*logm)\)
AC 代码
class Solution {
public:
int countDifferentSubsequenceGCDs(vector<int>& nums) {
int maxv = *max_element(nums.begin(), nums.end());
bool exist[maxv + 1];
memset(exist, false, sizeof exist);
for (int x: nums) {
exist[x] = true;
}
int count = 0;
for (int i = 1; i <= maxv; i++) {
// 枚举每一个数字是否可能成为最小公约数
int gcdv = 0;
for (int j = i; j <= maxv; j += i) {
// 只有当i的倍数(存在在数组中的)的最小公约数为i才可以
if (exist[j]) {
gcdv = gcdv ? gcd(gcdv, j) : j;
}
}
if (gcdv == i) {
count++;
}
}
return count;
}
};
总结
说实话没做出来的一部分原因是我有点畏惧 gcd (包括各种数论)的题目,但是解法就还蛮暴力的。另一个原因是我想到了这种方法但是自我否决了,主要是时间复杂度计算出错。确实这种复杂的时间复杂度计算我完全不会,还是需要加强这方面的能力。
相关文章
- 数据孤岛是业务效率的无声杀手
- 2023展望:新的一年将给大数据分析领域带来什么?
- 阿里云ADB基于Hudi构建Lakehouse的实践
- 大数据在医疗保健领域的使用案例
- 微软增加说明:KB5021751 更新扫描已经 / 即将过时 Office 过程中不会触碰用户隐私
- 2022 Gartner全球云数据库管理系统魔力象限发布 腾讯云数据库入选
- 场景化、重实操,分享一个实时数仓实践案例
- Arctic的湖仓一体践行之路
- 分布式计算MapReduce究竟是怎么一回事?
- 淘系数据模型治理优秀实践
- 大数据分析对医疗保健的影响
- 当我们说大数据Hadoop,究竟在说什么?
- 2022年及以后大数据的五个发展趋势
- 网易严选离线数仓治理实践
- 2023 年数据治理趋势
- 一份“靠谱”的年度经营计划,你学会了吗?
- 漫谈对大数据的思考
- 测试一下,读懂数据的能力,你有吗?
- 用艺术的眼光探索数据之美
- 聊聊数据分析成果如何落地