笨拙排序题解

考虑一个问题，如果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)

全部评论

相关推荐

头像
快来找我内推字节
05-09 13:38
字节跳动_商家运营
点赞 评论 收藏
转发
头像
犯困的牛油果已run
05-10 16:36
已编辑
University of Michigan Ann Arbor 计算机类
腾讯前端hr面还会挂吗！求oc！（附面经）
我已经想半场开香槟了，是可以的吗。hr面应该不会挂我了吧，球球了。在这里写一写面经攒人品！岗位是腾讯前端开发，经过三次一面一次二面现在在等hr面，这次的部门是腾讯广告。一面针对我做过的项目问了一些问题，包括bootstrap的tooltip怎么用，bootstrap和jquery的关系，jqeury使用了什么功能。然后问了一些别的，关于部署了解多少我说知道webpack但也没用过，还有输入url到浏览器显示的过程（好像经常问这个，我说tcp的时候还问了我三次握手和四次挥手的问题）。代码写的忘了。后面聊了一下部门使用什么开发工具，提到了react和less。一面还有什么问题有点忘记了，可以提一些...
点赞 评论 收藏
转发
头像
人狠话不多的椰子很友好
04-07 10:58
西安电子科技大学 电子信息类
点赞 评论 收藏
转发
头像
谷欠
03-17 14:21
南阳师范学院 计算机类
点赞 评论 收藏
转发
头像 会员标识 头像
sorano_
05-09 17:21
门头沟学院 计算机类
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议
# 牛客帮帮团来啦！有问必答 #
685779次浏览 11266人参与
# 市场营销面经 #
3953次浏览 114人参与
# 2022届毕业生现状 #
315502次浏览 4396人参与
# 你会选择考研还是直接就业 #
74634次浏览 854人参与
# 我的上岸简历长这样 #
160750次浏览 3213人参与
# 无实习如何秋招上岸 #
219549次浏览 3433人参与
# 浅聊一下我实习的辛苦费 #
79845次浏览 742人参与
# 你的简历改到第几版了 #
298846次浏览 4513人参与
# 投了多少份简历才上岸 #
55726次浏览 940人参与
# 软件开发投递记录 #
465751次浏览 7117人参与
# 运营面经 #
10473次浏览 261人参与
# 科大讯飞求职进展汇总 #
36057次浏览 365人参与
# Offer比较，你最看重什么？ #
49433次浏览 479人参与
# 毕业后不工作的日子里我在做什么 #
51982次浏览 687人参与
# 夸夸我的求职搭子 #
63577次浏览 774人参与
# 租房前辈的忠告 #
32664次浏览 2067人参与
# 秋招开了，你想投哪些公司呢 #
116211次浏览 3241人参与
# 硬件人的简历怎么写 #
77263次浏览 780人参与
# 写简历别走弯路 #
285935次浏览 3514人参与
# 产品面经 #
22119次浏览 426人参与
牛客网
牛客企业服务