java吧 关注:1,295,207贴子:12,831,052

今天碰见的面试题大佬来解答一下

只看楼主收藏回复

一个公司举行羽毛球比赛,共有1001人参加,选出最厉害的一个人,问需要多少场比赛?


IP属地:陕西来自Android客户端1楼2017-08-24 18:29回复


    IP属地:陕西来自Android客户端3楼2017-08-24 18:34
    回复
      2026-01-20 08:22:22
      广告
      不感兴趣
      开通SVIP免广告
      顾名思义 冒泡赛


      IP属地:江苏来自Android客户端4楼2017-08-24 18:37
      收起回复
        要是a干掉b,b干掉c,c干掉a呢


        IP属地:罗马尼亚来自iPhone客户端5楼2017-08-24 18:44
        收起回复
          有点像二分法查找,最大查询次数是log2(n)向上取整


          IP属地:安徽7楼2017-08-24 18:52
          收起回复
            这个是1vs1淘汰一个吗


            来自手机贴吧8楼2017-08-24 19:13
            收起回复
              把第一个人作为max在与逐个比较大的付给max


              IP属地:北京来自iPhone客户端9楼2017-08-24 19:41
              收起回复
                1000次比较
                选择排序,第一趟比较下来就能找到能力最强的选手。
                第一趟一共比较了(1001-1)次。


                11楼2017-08-24 20:13
                收起回复
                  2026-01-20 08:16:22
                  广告
                  不感兴趣
                  开通SVIP免广告
                  为什么我不能回复这个帖子?


                  13楼2017-08-24 20:16
                  收起回复
                    这题不好说啊,看球的都知道,有的对手就克这个人…


                    来自iPhone客户端14楼2017-08-24 20:17
                    回复
                      每比一场,就淘汰一个人。比1000场,淘汰1000个人,剩下的就是第一名


                      IP属地:湖北来自iPhone客户端19楼2017-08-24 20:52
                      回复
                        每次比赛淘汰一个人,一共需要淘汰1000个人,所以需要1000场比赛。


                        IP属地:上海22楼2017-08-24 21:12
                        回复
                          不懂就上百度搜呗


                          来自Android客户端24楼2017-08-24 21:16
                          回复
                            刚才发了那么多贴实在抱歉,不是故意的,今天的网络出了点问题。
                            我个人理解:
                            楼上说冒泡排序选择排序思路是都对的,
                            "找出1001个人里实力最强的选手"
                            等价于
                            "找到数组里值最大的那个元素"。
                            我想到了排序,冒泡排序和选择排序都有一种特性,每一趟排序下来都会确定一个最大或最小的元素。恰好解决了问题。
                            1001个元素数组的选择排序第一趟比较只需要(1001-1)次。


                            25楼2017-08-24 22:05
                            回复
                              2026-01-20 08:10:22
                              广告
                              不感兴趣
                              开通SVIP免广告
                              7楼吧友讲的二分查找不适用于这个问题。
                              二分查找作用于已经有序的数组上。
                              在本问题中如果数组已经有序这将意味着员工羽毛球实力排行榜已经存在。
                              那么找到实力最强的选手根本不需要再额外进行比赛,榜单第一名的员工实力最强。


                              26楼2017-08-24 22:10
                              收起回复