emptyCoder
2020-09-22 10:14 门头沟学院 Java
关注
第三题：
遍历时做1、2 操作
1、记录 pair 对（如<1, 2>，right>left）个数 为 p
2、维护一个 被选中 i 的邻接链表（倒排索引），以例子说明：
1 --> 1, 3, 4；2 ---> 2；3 ---> 2, 4； 4--->3
对 2 按 个数排序，然后双指针可得，包含重复的组合有 s = C(right - left + 1, 2)，其中 cnt[right] + cnt[left] >= k
去重（O(n)）：满足 cnt[a] + cnt[b] - p(共同选择) < k 的 pair 对 为 t， (容斥)
答案：s - t
查看原帖
1 4
相关推荐
查看12道真题和解析 02-19 20:11
门头沟学院 产品经理 
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 实习要如何选择和准备？ #
12326次浏览 270人参与
# 牛友们的论文几号送审 #
19741次浏览 538人参与
# 携程求职进展汇总 #
204364次浏览 1713人参与
# 美团求职进展汇总 #
1639782次浏览 14794人参与
# 如果你有一天可以担任公司的CEO，你会做哪三件事？ #
23088次浏览 448人参与
# 字节求职进展汇总 #
711131次浏览 7208人参与
# 比亚迪秋招开啦，你打算投递吗？ #
65498次浏览 558人参与
# 面试等了一周没回复，还有戏吗 #
98627次浏览 911人参与
# TCL求职进展汇总 #
102776次浏览 593人参与
# 运营人的第一份offer应该如何选 #
126753次浏览 1051人参与
# 机械人的工作环境真的很差吗 #
16203次浏览 104人参与
# 正在实习的你，几点下班 #
101913次浏览 735人参与
# 稳定和高薪机械人更看重哪个？ #
424065次浏览 5305人参与
# 科大讯飞工作体验 #
15765次浏览 48人参与
# 满分简历要如何准备？ #
18236次浏览 318人参与
# TCL提前批进度交流 #
28827次浏览 175人参与
# 面试被问第一学历差时该怎么回答 #
104542次浏览 659人参与
# 讲讲我的真实离职原因 #
33358次浏览 623人参与
# 听劝，这个公司值得去吗 #
406765次浏览 1564人参与
# 我想去国央企的原因 #
53282次浏览 327人参与
# 牛友打假中心 #
42472次浏览 2355人参与