pic*_*lbo 10
以下是Dialecticus的灵感来源.分成7个随机组并对每个组进行比赛,然后比赛这些组的中位数.这辆车成为枢纽,我们已经直接或间接地知道它与其他30辆汽车的关系(这是中位数中位数的属性).所以把它放在resp.另外18个我们需要进行3场比赛,包括枢轴.在转动之后,我们需要对最多33辆汽车进行递归.继续.我结束了29场比赛.即使你假设需要完全排序,但不是,在17场比赛中有一个下限(真正的下限甚至会更低),这远低于29.所以我怀疑这不是正确的答案,但由于这一点缺乏任何解决方案,因此这是一个次优的解决方案.如果你看一下关于分拣网络的研究(这个问题一次只限于两辆赛车),
也许一个例子可以帮助.让我们说从最慢到最快的车数,并将它们排列成7x7矩阵(任意,因为我们不知道速度,直到我们比赛它们).
[,1] [,2] [,3] [,4] [,5] [,6] [,7]
[1,] 34 25 45 43 26 21 13
[2,] 11 24 2 40 14 30 32
[3,] 27 19 29 42 4 17 46
[4,] 15 10 39 33 1 9 5
[5,] 28 18 41 8 23 20 6
[6,] 16 3 38 7 12 22 36
[7,] 31 44 48 35 49 37 47
然后让我们对每一列进行比赛,并根据比赛的结果对它们进行排序:
[,1] [,2] [,3] [,4] [,5] [,6] [,7]
[1,] 11 3 2 7 1 9 5
[2,] 15 10 29 8 4 17 6
[3,] 16 18 38 33 12 20 13
[4,] 27 19 39 35 14 21 32
[5,] 28 24 41 40 23 22 36
[6,] 31 25 45 42 26 30 46
[7,] 34 44 48 43 49 37 47
现在让我们参加第4排比赛(中位数)并根据结果重新排列
[,1] [,2] [,3] [,4] [,5] [,6] [,7]
[1,] 1 3 9 11 5 7 2
[2,] 4 10 17 15 6 8 29
[3,] 12 18 20 16 13 33 38
[4,] 14 19 21 27 32 35 39
[5,] 23 24 22 28 36 40 41
[6,] 26 25 30 31 46 42 45
[7,] 49 44 37 34 47 43 48
现在观察到中位数的中位数(元素[4,4])比上面和左边的任何一辆车都要快,并且比任何车辆的下方和右侧都慢(这是中位数中位数的属性).对于其他车辆(左下和右上)我们不知道,所以我们需要对抗[4,4],一次6场比赛(3场比赛).现在我们观察到26辆车比[4,4]慢,因此中位数必须是其中之一.无需再与任何其他人竞赛.现在用这26辆车重复这个过程.
Tom*_*das 10
我有一个只需要17场比赛的解决方案.
首先,让我解释一个需要32场比赛的简单解决方案.将赛车分为7组7人,每组比赛(7场比赛).重复25次:从每组中挑选剩余最快的车并将其输入比赛,并将获胜者(25场比赛)放在一边.25场比赛中的第一场确定了最快的整体赛车(#1),第二场比赛决定了#2,依此类推.
现在只有17场比赛的解决方案:
我们的策略是首先确定24辆最快的汽车(让我们称这些汽车"快速").然后我们会发现其余的最快(#25).
随机将汽车放置在7x7格栅上,并对每一排(7场比赛)进行比赛.然后,从每场比赛(第8场比赛)中争夺第3名选手,并按第3名终结者速度对行进行排序.
所以,经过8场比赛我们有这个:
每个网格单元代表一辆汽车.箭头指向更快的汽车.请注意,箭头是可传递的.
我们已经可以识别8辆"快速"汽车了:
我们怎么知道他们很快？看看蓝色的'x'.只有23辆车可能比它快(那些不在右下方的5x5).所以,它肯定是"快速的".您可以为其他x验证这一点.
我们已经确定了24辆"快速"汽车中的8辆.让我们从未来的考虑中删除这8个.我们现在正在寻找剩余车辆中最快的16辆.我们的七个小组的大小分别为4,4,5,7,7,7和7.(对于图表,每当我们移除一辆汽车时,让我们将剩余的汽车向左滑动.)
让我们比赛每组剩下第二快的赛车,并相应排序(第9场比赛).和以前一样,我们可以确定4辆车当然是最快的16辆(即"快速"):
我在拆除的汽车所在的牢房中着色,但这还没有效果.
我们已经确定了12辆"快速"汽车.删除"快速"汽车,我们寻找剩余汽车中最快的12辆.我们的小组的大小在2到7之间.让我们比赛每组剩下第二快的赛车,并相应排序(第10场比赛).我们确定了12辆车中最快的12辆(即"快速"):
(10"快速"汽车仍然存在.)
我们可以再重复上一步(第11和第12场比赛).每次我们再删除2辆车.但是,请注意,行/组中可能包含0或1个汽车.如果它有一辆车,我们比赛那辆车而不是"剩下的第二快车".如果那辆车获胜,我们知道它是"快速"的,以及下一个最快的第二名车.无论如何,我们确定了2辆"快速"的汽车.(剩下6辆"快速"汽车.)
经过12场比赛,我们确定并拆除了18辆"快速"赛车.我们需要确定剩余的6辆"快速"汽车.
现在让我们简单地比赛每组中最快的剩余赛车(第13场比赛),并相应地对行进行排序.获胜者是"快速".还剩5个.
在最后一场比赛之后,只有2辆车可能是剩下最快的车.蓝色的:
此外,剩余的第二快车辆是蓝色'o'或绿色'o'.让我们参加这5辆赛车比赛(第14场比赛),前两名选手肯定是"快速".还剩3个.
让我们重复最后两个步骤/比赛来确定最后3个快速赛车(第15和第16场比赛).
所以,我们确定了24辆"快速"汽车.剩余最快的汽车必须是第25快的.我们可以通过简单地在每排/每组(第17场比赛)赛车中找到这辆车.
小智 6
http://www.sureinterview.com/shwqst/1062001
第一回合
- (7场比赛)将赛车分成7组,并获得每组内的订单.
- (1场比赛)拿7位中位数并获得订单.找出中位数的中位数(表示为o).在下面的例子中,它是34.
- (3场比赛)找出中位数的中位数.从左下角(25~33)和右上角(13~21)取6个元素并与o(34)比赛.在3轮之后,我们知道整个集合中的中位数中位数.最好的情况是o是全球中位数(第25快).最糟糕的情况是o是第16或第34快.
此示例显示了一个可能的最坏情况.
1 2 3 4 13 14 15 <- group 1
5 6 7 8 16 17 18
9 10 11 12 19 20 21 ...
22 23 24 34 35 36 37
25 26 27 38 39 40 41 <- group 5
28 29 30 42 43 44 45 <- group 6
31 32 33 46 47 48 49 <- group 7
第二轮
我们希望以二分搜索方式找到其他中位数的等级.
- (3场比赛)选择小于34的中位数,即12.对着左下角和右上角的赛车进行比赛.经过3场比赛,我们知道它的排名是12.
现在,这两个中位数之间的差距最多为21,如本例所示.
第三轮
按如下方式重新排列21辆汽车(> 12和<34).
13 14 15 <- group 1
16 17 18
19 20 21 ...
22 23 24
25 26 27 <- group 5
28 29 30 <- group 6
31 32 33 <- group 7
每行仍然排序.
- (1比赛)再次找出中位数的中位数,即23.
- (1比赛)找到它的排名.在这一步之后,我们知道上一步中的汽车肯定排在第23位.
- (1比赛)类似于二分搜索,检查另一个中位数的等级,29.
- (1场比赛)将所有赛车排在23~29之间(独家).找到了第25辆最快的汽车.
所以最多需要18场比赛才能获得第25快的赛车.