笨拙排序题解

考虑一个问题,如果a[1]=x,至少需要操作几次?
如果a[1]=x的话,那么1到x-1都在a[1]后面,假设x+1到n在a[1]后面递增排列,抽出1到x-1之后x+1到n已经自然排好序了,所以当a[1]=x时至少需要x-1次操作。
当然以上结论有一个前提,是x+1到n递增排列,我们反过来想,找到某个y,使得y到n已经成递增排列,那么所需要的操作次数至多就是y-1次。
找到这个最小的y即可。
复杂度O(n)

全部评论

相关推荐

在看牛客的社畜很积极:身高体重那一行信息去掉,学校那一行的信息放上面,找半天都没找到你是哪个学校什么专业的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务