残缺的排列题解

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

全部评论

相关推荐

点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务