关注
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 评论
相关推荐
查看28道真题和解析 点赞 评论 收藏
分享
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 牛客吐槽大会 #
25468次浏览 323人参与
# 工作前VS工作后,你的心态变化 #
38498次浏览 267人参与
# 秋招想进国企该如何准备 #
125432次浏览 617人参与
# 你的mentor是什么样的人? #
51577次浏览 740人参与
# 从mentor身上学到了__ #
55611次浏览 886人参与
# 我和mentor的爱恨情仇 #
106679次浏览 968人参与
# 我的省钱小妙招 #
37593次浏览 446人参与
# 机械人避雷的岗位/公司 #
44842次浏览 320人参与
# 在大厂上班是一种什么样的体验 #
15117次浏览 224人参与
# 为了减少AI幻觉,你注入过哪些设定? #
7553次浏览 216人参与
# 职场上哪些行为很加分? #
323151次浏览 3618人参与
# 通信/硬件求职避坑tips #
139964次浏览 1087人参与
# 论秋招对个人心气的改变 #
16100次浏览 250人参与
# 你觉得mentor喜欢什么样的实习生 #
48747次浏览 1002人参与
# 你现在会用到哪些AI技能? #
24821次浏览 137人参与
# 牛客AI体验站 #
9333次浏览 230人参与
# 毕业论文进行时 #
27674次浏览 153人参与
# 运营来爆料 #
77442次浏览 467人参与
# 程序员找工作至少要刷多少题? #
24164次浏览 315人参与
# 过年最难忘的一件事 #
23327次浏览 179人参与