关注
T3
数组中求满足条件的对数:相同的数字或和能被m整除。
如果只有和能被m整除,我们可以维护一个长为m的数组mod_cnts,将数字按照模m的余数分组,然后遍历即可。现在多了一个可能的条件,我们可以把这个条件用另一个长为m的数组rep_cnts记录下来,rep_cnts[i]表示模m余i的数字中,两两相同的对数有多少。
那么当处理模m余i的数字时,和它成对的数要么在模m余i的集合中,要么在模m余m-i的集合中。对于模m余m-i的数字同理。那么我们优先让模m余i的数字和模m余m-i的数字两两结合,剩余的数字依据rep_cnts让它跟自己结合。
时间复杂度O(max(m, n)),空间复杂度O(max(m, n))。
查看原帖
1 评论
相关推荐
今天 18:08
National University of Singapore 运营 点赞 评论 收藏
分享
桐原j:学院本 不容易
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 如何准备秋招 #
9273次浏览 164人参与
# 软开人,秋招你打算投哪些公司呢 #
100534次浏览 944人参与
# 现代汽车前瞻技术研发急速编程挑战赛 #
21652次浏览 184人参与
# 你觉得实习能学到东西吗 #
13625次浏览 333人参与
# 每个月的工资都是怎么分配的? #
12833次浏览 284人参与
# 实习,不懂就问 #
25556次浏览 402人参与
# 秋招什么时候开投比较合适? #
5546次浏览 124人参与
# 你觉得现在还能进互联网吗? #
4108次浏览 97人参与
# 预测一下26届秋招形势 #
21222次浏览 218人参与
# 技术岗笔试题求解 #
75319次浏览 974人参与
# 聊聊你的职场新体验 #
161189次浏览 1391人参与
# 你最近一次加班是什么时候? #
67672次浏览 346人参与
# 高考出分的那一天,我__ #
14620次浏览 245人参与
# 打工人的精神状态 #
53545次浏览 973人参与
# 机械实习一天多少钱合适? #
28765次浏览 176人参与
# 米哈游工作体验 #
17565次浏览 116人参与
# 非技术岗简历怎么写 #
216543次浏览 2915人参与
# 你们公司几号发工资 #
18747次浏览 118人参与
# 你觉得实习只能是打杂吗? #
192084次浏览 1213人参与
# 来聊聊你认为的薪资天花板是哪家? #
30707次浏览 174人参与
# 安利/避雷我的专业 #
75876次浏览 522人参与