关注
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 评论
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
01-16 11:50
浙江工商大学 Java 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 牛客新年AI问运 #
2493次浏览 66人参与
# 刚工作,应该先搞钱or搞成长? #
20755次浏览 159人参与
# 牛客AI体验站 #
15489次浏览 275人参与
# 你觉得第一学历对求职有影响吗? #
229841次浏览 1266人参与
# 找工作中的小确幸 #
80331次浏览 448人参与
# 你觉得技术面多长时间合理? #
168032次浏览 1170人参与
# 实习在多还是在精 #
82681次浏览 509人参与
# 月薪多少能在一线城市生存 #
136339次浏览 898人参与
# 牛友的春节生活 #
11028次浏览 213人参与
# 备战春招/暑实,现在应该做什么? #
7523次浏览 199人参与
# 从夯到拉,锐评职场mentor #
7264次浏览 108人参与
# 实习到现在,你最困惑的一个问题 #
6538次浏览 164人参与
# 春招什么时候投? #
12890次浏览 208人参与
# 制造业的秋招小结 #
143306次浏览 2089人参与
# 电网笔面经互助 #
59646次浏览 476人参与
# 秋招踩过的“雷”,希望你别再踩 #
185625次浏览 1683人参与
# 春节提前走,你用什么理由请假? #
13155次浏览 288人参与
# 距离春招还有一个月,你现在是什么开局? #
9077次浏览 132人参与
# 今年秋招你收到了多少封邮件? #
38235次浏览 280人参与
# 暑期实习什么时候投? #
9276次浏览 197人参与

