美文网首页
腾讯面试题:64匹马,8赛道,找出最快的4匹最少要几次?

腾讯面试题:64匹马,8赛道,找出最快的4匹最少要几次?

作者: 眼若繁星丶 | 来源:发表于2021-04-20 21:13 被阅读0次

    初步思考

    • 64匹马,8赛道,很容易想到一直 除以8,显然会有很多重复的比较。
    • 还有一个大前提,所有的马都至少要跑一次,这样才能纳入统计。

    分析

    • 每一匹都得先跑一次,64匹,8个赛道,那就先分8组跑8次。
    image.png
    • 每一组都会得到8匹的相对速度,也就是在同一组内的名次。
    image.png
    • 为了方便描述,我们用编号来表示。其下标表示名次
    image.png
    • 只需要找前四,所以每组的后四名都被淘汰,不需要再比。「此时已经比了8场
    image.png
    • 现在每一组内都有相对名次,但不同的组间是不知道的。如果把A组和B组放一起,下面的情况都可能存在。
    image.png

    📌注:接下来是缩小比较次数的关键:选择每组的第一名再出来跑一次。落后的第一名所在的整组都可以排除。

    • 为了描述方便,把最快到最慢的第一名所在的组依次重新命名为A,B...H组。「这里比了1场
    image.png
    • 一样取前四,后面四整组都被淘汰。「因为他们组的第一名都被淘汰了,组员肯定都被淘汰」

    • 这时候已经确定了最快的马,「A1」。然后就可以在剩下 15 只马中排除一些不可能是总体前4的马。分别是「B4」「C3 C4」「D2 D3 D4」,如下图所示。

      • 可以这样理解,A1是第一名,所在的组都是「精英组」,理论上是可能A组4匹马都是前4,所以都保留名额,其他组同样思考。假设A组只有A1进入前4,B组全员进名次,这样就不可能排到B4,所以排除「B4」。同理,剩下的C组D组都可以这样思考,注:C组判断时,A1和B1肯定都在C组全员之前的
    image.png
    • 剩下的9匹马选3只即可。赛道只能放8匹马,这里先把「A4」这匹马放一边,然后剩下的进行比较。
      • 如果「A3」在第三名或更后,说明那3名已经选出来了「A4」不需要再跑了。「这样就是10场
      • 否则,再拉「A4」跟前三再比一场,这样即可选出三个名额。「这样就是11场
    image.png

    总结

    • 最少需要10场。
    • 最多需要11场。
    • 就可以把前4名选出来。

    图源:小K算法

    相关文章

      网友评论

          本文标题:腾讯面试题:64匹马,8赛道,找出最快的4匹最少要几次?

          本文链接:https://www.haomeiwen.com/subject/rflolltx.html