残缺的排列题解

首先我们可以明确的是，除了已经规定好相对顺序的m个数，其他数肯定按照从小到大的方式填最优。
接着根据这个思路，我们有一个这样的算法：
一开始我们将剩下的n-m个数放进堆(小根堆)里，然后将m个数中的第一个数放进堆中并给这个数做标记，每次弹出堆顶并输出，当弹出了做过标记的数时，往堆中放入m个数中的第二个数并做标记......知道m个数全部放进堆中且堆被弹空。
这个算法同时保证了其他数按照从小到大的顺序，且同时保证了m个已知数的相对顺序。
复杂度O(nlogn)

全部评论

相关推荐

今天 12:00
已编辑
小米_开发(准入职员工)
点赞 评论 收藏
分享
11-20 15:36
北京外国语大学 产品经理
点赞 评论 收藏
分享
09-26 12:03
华中科技大学 单片机
秋招首蚌
SinyWu：七院电话面的时候问我有没有女朋友，一听异地说你赶紧分。我:？？？
点赞 评论 收藏
分享
11-20 09:10
电子科技大学 前端工程师
点赞 评论 收藏
分享
点赞 收藏 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
236988次浏览 1938人参与
# 学历or实习经历，哪个更重要 #
40172次浏览 292人参与
# 北方华创开奖 #
22137次浏览 251人参与
# 地方国企笔面经互助 #
2394次浏览 6人参与
# 你最想要的公司福利是？ #
38319次浏览 85人参与
# 选完offer后，你后悔学本专业吗 #
8720次浏览 58人参与
# 应届生被毁约被毁意向了怎么办 #
25936次浏览 235人参与
# 机械应届生薪资要多少才合适？ #
12208次浏览 59人参与
# 查收我的offer竞争力报告 #
15458次浏览 210人参与
# 一觉醒来，我觉醒了超级打工人系统 #
2634次浏览 32人参与
# 没有实习经历，还有机会进大厂吗 #
804135次浏览 13798人参与
# 你觉得第一学历对求职有影响吗？ #
14750次浏览 121人参与
# 我的工作日记 #
20896次浏览 270人参与
# 不给转正的实习，你还去吗 #
1515114次浏览 16959人参与
# 寒假躺平还是提前实习 #
57770次浏览 424人参与
# 秋招OC许愿 #
225528次浏览 1861人参与
# 秋招被确诊为…… #
52306次浏览 292人参与
# 如何一边实习一边秋招 #
983583次浏览 12570人参与
# 总结:哪家公司面试体验感最差 #
25000次浏览 121人参与
# 公司情报交流地 #
31417次浏览 222人参与
# 面试题刺客退退退 #
136212次浏览 2082人参与
牛客网
牛客企业服务