两道算法面试题

zhiyajun11 2012-03-13 10:32:39

1、有81个选手，9个赛道，要求选出前4名。需要多少场？

2、有N（很大）个数，从里面选出第K（很小）大的数，要求时间复杂度尽可能的小。

...全文

4064 67 打赏收藏转发到动态举报

写回复

用AI写文章

67 条回复

切换为时间正序

请发表友善的回复…

发表回复

小刀刀 2012-03-20

打赏
举报

答案：11足够

分析：我们作此题的前提是所有选手的水平都必须是稳定的哦，不然是没有可以比较性的！所以没有偶然性！
>: 首先分成9组，每组9人跑一次，那么就是9场，那么我们每组只取4个人( 你懂的～ )
>: 然后将9组的第一名跑一次，排处前4名的组！那么需要1场
>: 现在有人：
第一名组：1 1 1 1 //4个人
第二名组：1 1 1 //3个人：因为至少第一名组的第一名是必须在4人中的，所以第二组最多3人
第三名组：1 1 //2个人，和2的解释一样，至少第一名组的第一名和第二名组的第一名
第四名组：1 //1个人，极端情况，只取第一名4个

那么现在剩下的是10人，又因为第一名组的第一名肯定是全组第一，所以不要跑，所以剩下9人跑一次，那么在加一次
所以 9 + 1 + 1 == 11

ok、、、

那一片海 2012-03-20

打赏
举报

13场
分9组去出每组的第一名，然后将9个第一名跑一场取出前四名。将这前四名小组的前四名取出，总共是16人，分3场跑完。
那么就是：9+1+3=13。

_YoungRay 2012-03-20

打赏
举报

第二题用随机快速选择法，时间复杂度为0(n)

yuqaf1989 2012-03-20

打赏
举报

第二题，设一个最大或者最小值，然后遍历数组，依次次比较，设个count值就能出来了，o（n）。

haiming80 2012-03-20

打赏
举报

第一题：9场就够了，单独给每个队员计时，比较结果而已

sevancheng 2012-03-19

打赏
举报

简单，能满足要求就可以
9场足矣。。。
出这种题扯淡。。。

hp641298897 2012-03-19

打赏
举报

看了上面的题目，我才知道我连编程思想都忘记的一干二尽了.

wangluolang520 2012-03-19

打赏
举报

嗯~需要11场~第一轮得出9个第一，这是9场，然后9个第一进行一次比赛。得出9个第一的顺序，按9个第一的最后顺序排出一道九组。
第一组：1 2 3 4
第二组：1 2 3
第三组：1 2
第四组：1
把除第一组第一名外的人进行一次比赛，就可以得出前4名了。

Sylla 2012-03-18

打赏
举报

只要10场啊

liulefirst 2012-03-17

打赏
举报

[Quote=引用 13 楼 litaoye 的回复:]

分9组先跑9场小组赛，再用9个第1跑1场决赛，共10场，此时可以确定的只有第1名。
那么2至4名有可能是谁呢？

特殊情况下，有可能1-4名都被分到了同一组，并且在小组赛里，2-4已经被淘汰了，因此需要把他们找回来。找到小组赛中输给冠军的2-4名，共3匹马。同理找到小组赛输给第2的2、3名，2匹马。输给第3的第2名，1匹马。如果2-4名是在小组赛中被淘汰了，那么只可能在这6匹马中。用这6匹……
[/Quote]看来我的理解狗屎了。

liuzhanchen1987 2012-03-17

打赏
举报

为什么内人纠结一下第二题呢？o（n）解决的给个方案？是1*n还是k*n还是x*n？如果是1*n的麻烦给个方案。

善良的八个鸭鹿 2012-03-17

打赏
举报

[Quote=引用 11 楼 gdujian0119 的回复:]

第一题没说清楚吧，我也可以说一场，81个在一个赛场跑，去前四名。
[/Quote]

你这个就有些牵强了，题目中说是9个赛道，明摆着一个赛道一个人啊！要不这样，分成9组，赛9场，得到每组第一名，然后9个人再赛一场，一共10场

孤独小剑 2012-03-17

打赏
举报

[Quote=引用 57 楼 gttd2012 的回复:]

引用 11 楼 gdujian0119 的回复:

第一题没说清楚吧，我也可以说一场，81个在一个赛场跑，去前四名。

你这个就有些牵强了，题目中说是9个赛道，明摆着一个赛道一个人啊！要不这样，分成9组，赛9场，得到每组第一名，然后9个人再赛一场，一共10场
[/Quote]是我看错了，分析了下，得到十一场可得结果
http://blog.csdn.net/gdujian0119/article/details/7364193

Jamy325 2012-03-17

打赏
举报

9场之后， 81个人的成绩都有了，直接算前4就行了

ssdsfdsfs 2012-03-16

打赏
举报

81/9=9 9/9=1,再加上输给预赛第一的2,3,4名，输给预赛第二的2,3名，再加上预赛第三的2共6名，再和预赛前3名，加赛一场，共11场

1/2n+(1/2)^2 *n+.....一直下去

a574772622 2012-03-16

打赏
举报

[Quote=引用 40 楼 iukey 的回复:]
你们咋就这么傻呢？ 9场就够了因为赛跑都是计时的哈。。。

开玩笑哈。不过也不是开玩笑，这个题目有歧义。要分是否计时。。。
[/Quote]顶个。想到一块去了

s_evra 2012-03-16

打赏
举报

如果一个人需要跑两次的话，那么他这两次必须跑一样快

shux02 2012-03-16

打赏
举报

这不是脑筋急转弯，所以照着出题意思，前提应该是没有秒表，且不管几个人跑一次就算一次。
所以11场很简单。9组取得各自名次后，第10场取每组第一名跑一次，然后取第一人的那组2,3,4名，第二人的那组前3，第三人那组前2和第四人。这次决出的前3加上第一名就是所求。

九月恒心 2012-03-16

打赏
举报

第一题，要说最快的话，那就是9场，计时不就可以了

SurgePing 2012-03-16

打赏
举报

[Quote=引用 16 楼 lorry1113 的回复:]

引用 13 楼 litaoye 的回复:
分9组先跑9场小组赛，再用9个第1跑1场决赛，共10场，此时可以确定的只有第1名。
那么2至4名有可能是谁呢？

特殊情况下，有可能1-4名都被分到了同一组，并且在小组赛里，2-4已经被淘汰了，因此需要把他们找回来。找到小组赛中输给冠军的2-4名，共3匹马。同理找到小组赛输给第2的2、3名，2匹马。输给第3的第2名，1匹马。如果2-4名是在小组赛……
[/Quote]
是这么个特殊情况，通俗点，就是考虑到某小组的整体实力可能比其他小组实力强，不错