腾讯面试题。 985一条街来看看？

我觉得现代科技可以有秒表吧，所有马跑完一轮也就是8回合，看秒表就知道名次了。难不成现在学生跑步还要跑好几轮？

测速的话不是全都要跑一遍

8个回合。掐表跑完，排个1234么

1、64除以8，分8组跑，每组的1-8排名就出来了。
2、一共8个小组第一。拉一起跑一轮，根据排名分别编号为:A.B.C.D.E.F.G.H，A所在小组则为A组，以此内推。
3、EFGH你们进不了前四。你们的组也全部淘汰。什么？你们的组员有意见？你们当老大的都进不了前四，轮得到下面的渣渣？
3、A组的第二、三、四不服，老四觉得自己能赢B，前四全在自己组。
合理，安排！记一下：A组2.3.4名可以参赛。
4、B组的第二、三不服，可以，记一下啊：B组2.3名。（什么B组第4你还不服？比你强的已经有四个了：A和B组1.2.3）。
5、C组的第2也登记一下，C组第三你也别开口了，比你强的已经有AB和C组1.2了。
6、D你出来一下，现在在场的所有人都觉得能赢你。对了还有B和C，你们也来。A组说他们包揽前四。
7、新一轮参赛选手有：A组2.3.4，B组1.2.3，C组1.2，以及被所有人盯上的D。
8、哟，9个人啊，呸，是9匹马。那A组第四你出来一下，哟，还不乐意，就你叫夏洛啊。别急，你等着啊。
9、这一轮结束，取前三。加上A。你们就是前四了。如果A组第三，拿不到这一轮前二，夏洛啊，你还瞅啥，哪凉快哪待着去吧。
如果A组第三，拿到了这一轮第二，夏洛啊，给你个机会，还有你，别东张西望了，就是你：最后一轮的第三名，你们干一下试试。
完结撒花，纯手机手打。看ID，你们知道该怎么做

引用 @虎扑JR1375400214 发表的:
专业点，毕竟不是985一条街，一共跑11回合就OK了。
先随机分8组，取出每组前4。
然后让这8组的冠军跑一轮，留下前4名，这时候冠军已经确定了。剩下的4组舍弃。
然后取出冠军组的2,3、4名，
第二名组的1,2,3名
第三名组的1,2名
第四名组的1名。

这9匹马跑两次，取出前3就OK

8+1+2=11次

我不能跑8次计时去前4嘛

引用 @八宝不吃八宝粥 发表的:
我觉得9次就可以了，请指出我的错误，分成8组，每组第一名出来组成新的冠军组，冠军组比一次，选出前四名，一共9次，我思维有漏洞吗？

因为厉害的可能都在一组啊 中国男篮亚洲第一 世界杯小组赛都出不了线 一个道理

引用 @蓝血战士 发表的:
你是没看懂，冠军组第2，3，4只没和其他组的比过怎么得出比其他的快？冠军组第一比其他组第一快就能说明冠军组第2.3.4比组的快？

看清楚我回的谁，他说假如64匹中最快的四匹在同一组

引用 @Matere 发表的:
题就说的最少 我的理解就是beat case 可能平时看的都是英文所以中文题意有点区别? 算worst case 的话怎么也要提big o之类的吧？

最少的意思是至少

引用 @晚安花菜 发表的:
我只要前四，你这小组后四名比其他快有什么用？还能比本组前四名快？

有死亡小组的可能性 就像今年世界杯中国的分组 在一组的球队实力不是特别强 属于上上签

15回合

算法题这么有意思👍🏽

引用 @1131857504 发表的:
有死亡小组的可能性 就像今年世界杯中国的分组 在一组的球队实力不是特别强 属于上上签

你管他什么死亡小组，每组只取前四，意思是每一轮只淘汰每组后四名，你觉每组的后四名有机会进前四？有这么难理解吗？在家教小朋友做题脑壳疼，没想到还有这么多成年人和小孩一样头脑简单。

引用 @晚安花菜 发表的:
你管他什么死亡小组，每组只取前四，意思是每一轮只淘汰每组后四名，你觉每组的后四名有机会进前四？有这么难理解吗？在家教小朋友做题脑壳疼，没想到还有这么多成年人和小孩一样头脑简单。

怎么还是没明白呢 第一组的第五名一定比那些组的第四名成绩慢嘛？这是一定的吗 你说把跑8×8➕1 65次这种方法还行 你直接取前四就绝对不是一定的 如果你想要说我就要前四那些我不要 那也没办法你这不是取快的

引用 @晚安花菜 发表的:
你管他什么死亡小组，每组只取前四，意思是每一轮只淘汰每组后四名，你觉每组的后四名有机会进前四？有这么难理解吗？在家教小朋友做题脑壳疼，没想到还有这么多成年人和小孩一样头脑简单。

这种方法是完全不确定的

引用 @虎扑JR1375400214 发表的:
专业点，毕竟不是985一条街，一共跑11回合就OK了。
先随机分8组，取出每组前4。
然后让这8组的冠军跑一轮，留下前4名，这时候冠军已经确定了。剩下的4组舍弃。
然后取出冠军组的2,3、4名，
第二名组的1,2,3名
第三名组的1,2名
第四名组的1名。

这9匹马跑两次，取出前3就OK

8+1+2=11次

看半天终于懂了，不适合啊！

引用 @虎扑JR1375400214 发表的:
专业点，毕竟不是985一条街，一共跑11回合就OK了。
先随机分8组，取出每组前4。
然后让这8组的冠军跑一轮，留下前4名，这时候冠军已经确定了。剩下的4组舍弃。
然后取出冠军组的2,3、4名，
第二名组的1,2,3名
第三名组的1,2名
第四名组的1名。

这9匹马跑两次，取出前3就OK

8+1+2=11次

算完来看回复 果然找到了同解法

拿个表？8回合都出来了？

引用 @虎扑JR1375400214 发表的:
专业点，毕竟不是985一条街，一共跑11回合就OK了。
先随机分8组，取出每组前4。
然后让这8组的冠军跑一轮，留下前4名，这时候冠军已经确定了。剩下的4组舍弃。
然后取出冠军组的2,3、4名，
第二名组的1,2,3名
第三名组的1,2名
第四名组的1名。

这9匹马跑两次，取出前3就OK

8+1+2=11次

11个毛啊，拿个表计时，8个回合全跑一遍不就出来了，你们是读书读傻了吧，

八回合啊。。然后看时间选最快前四就行了

引用 @说气人不你 发表的:
明天报道

这个觉悟怕是当场就可以签约，三分钟后就可以上班了！

拼多多漏洞 不用邀请好友 点击链接跳到微信页面不用邀请直接返回 来回十几次到一百直接提现即可 亲测到账 一个手机号码可以领三次，我又领成功一次了😂😂
https://w.url.cn/s/ABPRkYg

引用 @稀饭范贩 发表的:
本人不是码农。感觉这种程序算法题都是在考数学啊，是不是数学好搞算法优势大。

计算机就是在搞数学

引用 @低调小卡戎 发表的:
看没人回你，借个楼吧🐶。
一共需要比赛11回合。
64匹马分八个小组，每组取前四。（剩32匹）
然后，这八个小组的“冠军马”赛一下，后四名“冠军马”所在的小组，整组淘汰，还剩四组马。（剩16匹）
第一名“冠军马”，所在小组取前4名马留下来。
第二名“冠军马”，所在小组取前3名马留下来。
第三名“冠军马”，所在小组取前2名马留下来。
第四名“冠军马”，所在小组只留第1名。
这时候还剩10匹马，最快的4匹绝对在这里。
最后，这10匹马，随机选8匹赛一次，取前四。然后用这四匹再加上剩下的两匹马，再赛一次，取前四名。那么这四名就是最快的四匹马了！8+1+1+1＝11
PS 我这么跑让老大多跑了两次，实在不好意思，但这样跑jrs们好理解啊🐶

这一个组的第五名比另一个组的第一名快怎么办

引用 @Rokami 发表的:
这一个组的第五名比另一个组的第一名快怎么办

咱只选最快的四匹马就行了，第五名它爱咋咋滴🐶

引用 @Rokami 发表的:
这一个组的第五名比另一个组的第一名快怎么办

选前四，第五名可以领盒饭

最少一个回合啊，最快的8匹马一起跑，前4就是

先分8组跑8轮，剩32匹，第9轮8个冠军跑一遍，剩10匹，并找出最快的1匹，9选3，第10轮冠军组的第二名跑一遍，大部分可能都可以找出最快的四匹，除非第十轮的前三刚好都是头马那组的，那就要轮空的一匹跟第四名再跑一轮，所以最少10轮，最多11轮可以找出最快的4匹

引用 @Matere 发表的:
用quicksort最快九次😏

没有计时没法弄

话说不能用秒表记一下吗？每一匹马跑一次就出来了啊

引用 @RuizFatty 发表的:
如果其中一组第二名成绩好过其他组第一名呢？

看不懂字，后面那两轮不在比了吗？

引用 @小冰狗 发表的:
那头叫化腾的跑得最快，叫云的最后一名🐶

笑死我了

十一场 前八场分八组所有马跑一遍。
第九场 八组每组第一名比 选出第一
第十场 最快那组的第二名 第三名 第四名 和 第二快组的第一名 第二名 第三名 和 第三快组的第一名 第二名 这里分两种情况
如果排名是 第二快组第一名 > 第三块组第一名> 其他，则决出前三名 第四名需要第十一场：第一快组第二名和第四快组第一名比较；
如果排名是 其他 则不需要比较。十场决出前四名

每匹马跑一轮就可以了啊，64匹马分八个小组跑一次，每匹马跑的时间就有了，取时间最短的四匹马不就行了？

4轮就行

4匹马，如图

理论上最快是10次

引用 @携带电话 发表的:
你就扯吧，那我说一次都不测就可以，我抽四匹马就可能正好是最快的

他不是叫你测，最少几次，一次

这不是归并排序吗

我是腾讯的 但这道题真不会（狗头）

8次，按所用的时间一排不就知道了。

引用 @说气人不你 发表的:
明天报道

应该是充会员的最快

可以树状图推论啊。 随机选8匹马为一组。 取第一名。在随机选7匹马加上第一组第一名赛。 看弟2组第一组的第一名为第几。分情况讨论 要是第一名就继续参加第三组 弟2名由第二组第一名参加下一组比赛 保留下来234名观察 第三名也由第一名参赛第三组 保留34名马 第4名也是由弟2组第一名参赛第三组 保留下4号马。 第三组及以后情况以此类推。 出现最坏情况。第一组马每组第一。则第一马晋级。 选择第一组2号马和第三组以后第2名跑 多出一个晋级。然后第3名都跑多一名 第四名都跑多一名。 取个组第一名以及随机晋级马。8马参赛。取前3名加第一名。 共计13次。

引用 @说气人不你 发表的:
明天报道

可以树状图推论啊。 随机选8匹马为一组。 取第一名。在随机选7匹马加上第一组第一名赛。 看弟2组第一组的第一名为第几。分情况讨论 要是第一名就继续参加第三组 弟2名由第二组第一名参加下一组比赛 保留下来234名观察 第三名也由第一名参赛第三组 保留34名马 第4名也是由弟2组第一名参赛第三组 保留下4号马。 第三组及以后情况以此类推。 出现最坏情况。第一组马每组第一。则第一马晋级。 选择第一组2号马和第三组以后第2名跑 多出一个晋级。然后第3名都跑多一名 第四名都跑多一名。 取个组第一名以及随机晋级马。8马参赛。取前3名加第一名。 共计13次。

引用 @木古女未子 发表的:
让你打工，不是来当领导的

可以树状图推论啊。 随机选8匹马为一组。 取第一名。在随机选7匹马加上第一组第一名赛。 看弟2组第一组的第一名为第几。分情况讨论 要是第一名就继续参加第三组 弟2名由第二组第一名参加下一组比赛 保留下来234名观察 第三名也由第一名参赛第三组 保留34名马 第4名也是由弟2组第一名参赛第三组 保留下4号马。 第三组及以后情况以此类推。 出现最坏情况。第一组马每组第一。则第一马晋级。 选择第一组2号马和第三组以后第2名跑 多出一个晋级。然后第3名都跑多一名 第四名都跑多一名。 取个组第一名以及随机晋级马。8马参赛。取前3名加第一名。 共计13次。

引用 @一块奶油小饼干 发表的:
每组第一的一起跑，跑完选出最快的，假设是a组，此时把a组第二拉出来，和原来七个跑，再把最快的拉出来，以此类推，前一个最快的选出来，该组下一名顶上，选出四个最快的，这种方法就是跑12次，不知道还有没有更快的，坐等

可以树状图推论啊。 随机选8匹马为一组。 取第一名。在随机选7匹马加上第一组第一名赛。 看弟2组第一组的第一名为第几。分情况讨论 要是第一名就继续参加第三组 弟2名由第二组第一名参加下一组比赛 保留下来234名观察 第三名也由第一名参赛第三组 保留34名马 第4名也是由弟2组第一名参赛第三组 保留下4号马。 第三组及以后情况以此类推。 出现最坏情况。第一组马每组第一。则第一马晋级。 选择第一组2号马和第三组以后第2名跑 多出一个晋级。然后第3名都跑多一名 第四名都跑多一名。 取个组第一名以及随机晋级马。8马参赛。取前3名加第一名。 共计13次。

引用 @遥隔_云端 发表的:
算法题啊。。

可以树状图推论啊。 随机选8匹马为一组。 取第一名。在随机选7匹马加上第一组第一名赛。 看弟2组第一组的第一名为第几。分情况讨论 要是第一名就继续参加第三组 弟2名由第二组第一名参加下一组比赛 保留下来234名观察 第三名也由第一名参赛第三组 保留34名马 第4名也是由弟2组第一名参赛第三组 保留下4号马。 第三组及以后情况以此类推。 出现最坏情况。第一组马每组第一。则第一马晋级。 选择第一组2号马和第三组以后第2名跑 多出一个晋级。然后第3名都跑多一名 第四名都跑多一名。 取个组第一名以及随机晋级马。8马参赛。取前3名加第一名。 共计13次。

一轮。看谁跑完用的时间少

我寻思着，分八组，计个时不就ok了🐴？

引用 @启动超级变化 发表的:
可以树状图推论啊。 随机选8匹马为一组。 取第一名。在随机选7匹马加上第一组第一名赛。 看弟2组第一组的第一名为第几。分情况讨论 要是第一名就继续参加第三组 弟2名由第二组第一名参加下一组比赛 保留下来234名观察 第三名也由第一名参赛第三组 保留34名马 第4名也是由弟2组第一名参赛第三组 保留下4号马。 第三组及以后情况以此类推。 出现最坏情况。第一组马每组第一。则第一马晋级。 选择第一组2号马和第三组以后第2名跑 多出一个晋级。然后第3名都跑多一名 第四名都跑多一名。 取个组第一名以及随机晋级马。8马参赛。取前3名加第一名。 共计13次。

这么复杂。分成8组跑8次就够了

两头跑，一回合跑16匹马选4个一共四回合，再16个跑一下远4个，一共5次

不是跑八次，计时最快的四匹？

引用 @Matere 发表的:
题就说的最少 我的理解就是beat case 可能平时看的都是英文所以中文题意有点区别? 算worst case 的话怎么也要提big o之类的吧？

题目的意思是“最少多少次可以*保证*得到最快四匹马” worst case就是对应的“保证”这两个字 即用这个算法得到的结果一定正确 在这个基础上的最optimal的解法。要是不考虑“保证找到”只看“最少” 那我测一次取前4名也够了 毕竟运气好的话这4个就恰好是64个中的前4名。另外这和BigO一点关系都没有 那个是算法复杂度的概念 你这基础概念都不扎实 各种混淆。

宰了60匹马，剩余的4匹一定是最快的。

引用 @虎扑JR1375400214 发表的:
专业点，毕竟不是985一条街，一共跑11回合就OK了。
先随机分8组，取出每组前4。
然后让这8组的冠军跑一轮，留下前4名，这时候冠军已经确定了。剩下的4组舍弃。
然后取出冠军组的2,3、4名，
第二名组的1,2,3名
第三名组的1,2名
第四名组的1名。

这9匹马跑两次，取出前3就OK

8+1+2=11次

八个跑道正向加反向可以一次跑两组16匹马

最低10次 如果运气差点11次100%可以

引用 @晚安花菜 发表的:
你看懂了原层主的意思？我只需要4匹最快的，要排除什么组和组的差别？假如最快的都在A组，A组前四是不是一直打到决赛？你管别的组怎么样呢，虽然这个层主不是最少的，但是合理的。

明白人 ，别和他吵了。我快被他气死了hhh 怎么就和他说不通 一根筋。三季人

五回合，16个🐴88相反跑，每轮选最快那四个，四轮后剩最后16匹再跑一轮就得出最快四匹了

引用 @单车都几快窝 发表的:
this pony horse most fastest. the jack horse👋🌟

牛逼

引用 @虎扑JR1375400214 发表的:
专业点，毕竟不是985一条街，一共跑11回合就OK了。
先随机分8组，取出每组前4。
然后让这8组的冠军跑一轮，留下前4名，这时候冠军已经确定了。剩下的4组舍弃。
然后取出冠军组的2,3、4名，
第二名组的1,2,3名
第三名组的1,2名
第四名组的1名。

这9匹马跑两次，取出前3就OK

8+1+2=11次

正解，就是在空间复杂度有限的情况下计算最优时间复杂度的问题