首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
基础学习课
实战项目课
求职辅导课
专栏&文章
竞赛
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
AI面试、笔试、校招、雇品
HR免费试用AI面试
最新面试提效必备
登录
/
注册
尤里卡斯特
2018-04-02 15:20
已编辑
华南理工大学 算法工程师
关注
已关注
取消关注
头条面试的算法题,怎么解?
头条面试的时候问的算法题:
给定一个乱序的链表,现在有一个操作:可以把链表任意位置的值移动到链表的最后。求链表排序所需要的最少操作次数。
样例:
假如链表的值为:5 1 2 3 那么最少的操作次数为1,直接把5移到最后即可,输出为1.
再比如 链表值为 5 2 1 3 ,那么应该先把2移到最后,再把3移到最后,再把5移到最后,这样输出的结果为3.
怎么解?
#实习#
#面经#
提示
全部评论
推荐
最新
楼层
DmcDante
上海交通大学 Java
把链表所有值扔到一个最小堆,count计数为0,遍历链表找到和最小堆堆顶元素相等的节点,最小堆出堆,count计数+1,检测当前堆顶是否和下一个节点相等,相等的话重复上述操作,不相等说明链表中从最小节点开始符合全局有序的序列长度为count,需要移动的最小次数是总数n-count 如5 2 1 3 ,第一次堆顶为1,找到链表中1的位置,下一个堆顶元素为2,但是节点的下一个元素为3,不相等,所以最小移动次数为4-1=3,代码中注意下边界条件检测等问题应该就ok
点赞
回复
分享
发布于 2018-04-02 15:23
接下来的路才真正的开始
武汉科技大学 C++
举例:5 4 8 9 1 7 6 2 3 本质上就是找到最小的数,然后从最小的数开始一直到后面的最长有序序列。 首先找到最小数1。1左边的肯定要移动,直接不用管。 5 4 8 9 1 6 7 2 3 从1开始,6大于1,标记f1为5,即已排序的下标;标记f2为5,即为已遍历的下标。 7大于6,标记f1为6,f2为6。 2小于6,标记f1位5,f2为7,且序列变为5 4 8 9 1 2 7 2 3 3大于2,标记f1位6,f2为8,且序列变为5 4 8 9 1 2 3 2 3 最后用标记f1,即最后需要找的序列,减去最小数的下标,即为他的长度,也就是最小的数开始一直到后面的最长有序序列的长度m。所以最后的结果为 N(总长度)-m。
@尤里卡斯特
中间查找比较的时候可以用二分优化下。。
点赞
回复
分享
发布于 2018-04-03 10:17
lzslzslzs
山东农业大学 C++
先遍历一遍找到最小值min1,记录下来。 然后再次遍历,找到min1左边部分的最小值min2。 记录min1右边部分有多少个数大于min2,记为cnt。 最后结果即为 左边部分数量+cnt 时间复杂度为O(n),;使用了3个int(longlong),空间复杂度为常数阶
点赞
回复
分享
发布于 2018-04-03 00:39
接下来的路才真正的开始
武汉科技大学 C++
时间空间要求? 假设 5 4 8 9 1 7 6 3 首先找到排序 1 3 4 5 6 7 8 9 然后和原始数列进行对比发现,从最小数1开始。 发现只有1 3满足要求,即1 3不动, 其他数从小到大依次往后移。 所需移动次数未8-2=6,移动如下: 5 8 9 1 7 6 3 4 8 9 1 7 6 3 4 5 8 9 1 7 3 4 5 6 8 9 1 3 4 5 6 7 9 1 3 4 5 6 7 8 1 3 4 5 6 7 8 9
点赞
回复
分享
发布于 2018-04-02 16:43
山柴贩
浙江大学 Java
https://www.nowcoder.com/questionTerminal/adc291e7e79f452c8b59243a5ce68d3a 和这个题类似的
点赞
回复
分享
发布于 2018-04-02 16:17
anonk
鄂州职业大学 C++
5 -> 1 -> 2 -> 3 提供参考思路,时间复杂度O(n), 空间复杂度O(1) 1. 找链表的最小值,比如1,指针为lo,count=1 2. 找lo前面的最小值为5,查找一次就ok 3. 从lo开始往后找,找lo后面的最小值为2,对比2和5,比前面的最小值5小,count++,lo设置为2,重复第3步 4. 如果第3步中向后遍历的值比5大,可以结束了,答案就是 链表长度-count。
点赞
回复
分享
发布于 2018-04-03 10:21
已删除
你有没有问条件,比如这n个数范围,是范围内随机数,还是1-n,是有重复还是没有重复数字,单链表还是双向链表,条件不同,做法就不同
点赞
回复
分享
发布于 2018-04-02 21:28
=..=
腾讯_天美_研发工程师(准入职)
空间是O(1)应该是有条件的,猜测是数字从1-n连续,其实就是给了你排好序的数组,把链表遍历一遍,记录不需要变的个数count,n-count就行了
点赞
回复
分享
发布于 2018-04-02 19:55
尤里卡斯特
楼主
华南理工大学 算法工程师
头条的算法题,真难!
点赞
回复
分享
发布于 2018-04-02 19:42
加满油go
华南理工大学 算法工程师
我觉得思想可能是首先从最小的数查找,从它开始查看下一个是否是比它大的最小的数,如果是继续寻找,如果不是,1则找到比它大的最小的数把排到最后,然后比他大的都要排一次最后,所以我觉得总次数为:假如前m个数为紧挨升序排列,则最小排列次数为(n-m),n为总个数。
点赞
回复
分享
发布于 2018-04-02 19:00
海量hc
中山大学 算法工程师
双指针?空间复杂度O(1)我也不知道 def f(nums): sortnums = sorted(nums) n = len(nums) i = nums.index(min(nums)) j = 0 if i == n - 1: return n - 1 while i < n and j < n: if nums[i] == sortnums[j]: i = i + 1 j = j + 1 else: i = i + 1 return n - j
点赞
回复
分享
发布于 2018-04-02 18:00
小罐球
浙江大学 算法工程师
//找到从最小值开始的最长有序序列,动规遍历一遍,碰到更小的值归零? int count; int curmin = 0; int dp[N]; for(int i = 0; i < N; i++){ if(a[i] > curmin){ if(a[i] > a[i] - 1){ dp[i] = dp[i - 1] + 1; } else{ dp[i] = dp[i - 1]; } } else{ curmin = i; dp[i] = 0; } } count = N - dp[N-1];
点赞
回复
分享
发布于 2018-04-02 17:30
已删除
一个数前面有比它大的数,那么这个大的数必须移一次 找出所有需要移的数,按从小打到依次往后移 用stack来实现
点赞
回复
分享
发布于 2018-04-02 15:45
Juliiii
中山大学 C++
头条的算法题真是一题比一题惊心
点赞
回复
分享
发布于 2018-04-02 15:13
暂无评论,快来抢首评~
相关推荐
07-07 15:18
门头沟学院 Java
作为实习生,我问薪无愧
小小的老子在某互联网中厂做工前两天在即将下班之时我如同离弦之剑般打算从工位上发射出去,就在我站起来准备走的时候 mt突然叫住我 说有个活我直接拒绝 说明天上班再干 mt脸上出来一种微妙的表情此后两三天 mt都对我十分冷漠 但小小的老子绝不内耗打算干完这个月就离职就我一个小实习生的薪水我还要给你加班??拒绝加班我完全问薪无愧
码农索隆:
实习不转正,惯着他干嘛,叼他!!!
点赞
评论
收藏
分享
不愿透露姓名的神秘牛友
今天 12:05
广州找工作好难啊啊啊啊
再一次面试失败了,考虑去送外卖了,这可是我土生土长的地方
点赞
评论
收藏
分享
06-02 23:35
门头沟学院 后端
在 boss 上找到了好工作
六十块钱的发烧友,哈哈哈哈哈哈哈哈哈哈
门口唉提是地铁杀:
之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞
评论
收藏
分享
06-24 00:02
北京电子科技职业学院 活动运营
我叫谷兴阳,25年毕业,我的身体素质好,三观正,有良好的执行能力,绝对服从安排,性格稳重。
在卷行测的大卫很理性:
整个简历最有竞争力的就是北京籍贯
点赞
评论
收藏
分享
07-07 14:13
武汉大学 产品经理
哥的青春才几年,你试用期就十年
小叮当411:
应该是1-3个月吧
点赞
评论
收藏
分享
评论
点赞成功,聊一聊 >
点赞
收藏
分享
评论
提到的真题
返回内容
招聘动态
查看更多
现代汽车前瞻技术研发挑战赛
26届投递链接合集
快手
快Star-X特别技术人才计划启动
全站热榜
更多
1
...
🌟择难路,未有疑,四非学院本运气拉满,春招拿下大厂后端
5.8W
2
...
其实主包早就找到工作了,但还是每天都刷
7903
3
...
史上最细SQL实战系列:sql笔试例题总结篇(建议收藏)
7321
4
...
恋爱四年没想到过自己会出轨
6222
5
...
快star-x二面凉经
3979
6
...
小红书二面(第二天oc)
3552
7
...
离开软件测试才发现外面没有雨
3420
8
...
从天坑文科到大二腾讯的经历
3297
9
...
字节拒绝、百度毁约,7.1 腾讯 Offer 到手:25 届双非碎碎念(25届最晚Offer)
3132
10
...
25届毕业现在在家呆了一个多月,没工作
3077
创作者周榜
更多
正在热议
更多
#
计算机有哪些岗位值得去?
#
2895次浏览
31人参与
#
社会教会你的第一课
#
9009次浏览
131人参与
#
现代汽车前瞻技术研发急速编程挑战赛
#
42216次浏览
293人参与
#
实习生的蛐蛐区
#
13197次浏览
114人参与
#
神州信息工作体验
#
13766次浏览
64人参与
#
应届生,你找到工作了吗
#
9807次浏览
90人参与
#
被AI治愈的瞬间
#
57436次浏览
620人参与
#
说说你知道的学历厂
#
7928次浏览
66人参与
#
你认为小厂实习有用吗?
#
3534次浏览
42人参与
#
你找工作的时候用AI吗?
#
3261次浏览
33人参与
#
哪一瞬间觉得自己长大了
#
1964次浏览
38人参与
#
歌尔求职进展汇总
#
55857次浏览
335人参与
#
面试尴尬现场
#
5892次浏览
43人参与
#
下班后的时间你怎么安排
#
1714次浏览
25人参与
#
简历当中有水分算不算造假?
#
11310次浏览
116人参与
#
双非应该如何逆袭?
#
180990次浏览
3152人参与
#
秋招盘点:机械人值得去的企业
#
74026次浏览
671人参与
#
毕业旅行去哪玩儿
#
10405次浏览
130人参与
#
三一集团提前批进度交流
#
24467次浏览
139人参与
#
秋招想进国企该如何准备
#
72057次浏览
416人参与
#
没有合适的工作,你会先找个干着,还是考公考研
#
118244次浏览
1134人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务