第一步：把所有的數(shù)字放到二叉樹(shù)的葉子結(jié)點(diǎn)，然后按照錦標(biāo)賽單淘汰的方式，兩兩比較選出最大的。
第二步：對(duì)于第二大的，從所有被最大的數(shù)字淘汰的數(shù)字中選擇。比如在某次比賽中被RNG淘汰的是FW，KT等戰(zhàn)隊(duì)，那么這些戰(zhàn)隊(duì)在進(jìn)行單淘汰，選亞軍。對(duì)于第三第四大的數(shù)字，可以以此類(lèi)推。
按照這種方式將所有的數(shù)字排序，算法的復(fù)雜度，或者說(shuō)量級(jí)是N乘以L(fǎng)ogN，和快排差不多。那么為什么不直接使用快速排序，而要發(fā)明出這么一種不太容易理解的算法呢？因?yàn)樵谔囟ǖ膱?chǎng)合下他更快速。比如說(shuō)，如果我們只需要選出第一名，這種算法的復(fù)雜度只有N，不是N乘以L(fǎng)ogN，如果要選出第二名，則額外加上LogN次計(jì)算就可以了，對(duì)第三名也是如此。也就是說(shuō)，這種方法在從N個(gè)選手中選出K個(gè)選手的事情特別快。
有了上述算法，我們講解下高盛和Google的面試題了，當(dāng)然任何算法用于實(shí)際的問(wèn)題，都需要變通一下。
假定有二十五名短跑選手比賽競(jìng)爭(zhēng)金銀銅牌，賽場(chǎng)上有五條賽道，因此一次可以有五個(gè)人同時(shí)比賽。比賽并不計(jì)時(shí)，只看相應(yīng)的名次。假如選手的發(fā)揮時(shí)穩(wěn)定的，也就是說(shuō)如果約翰比張三跑的快，張三幣凱利跑的快，那么約翰一定幣凱利跑的快。最少需要幾組比賽才能決出前三名？
第一步：25名選手分成五組，為了便于說(shuō)明我們把25人根據(jù)所在的組進(jìn)行編號(hào)，A1-A5在A(yíng)組，B1-B5在B組...最后E1-E5在E組。
然后讓各組分別比賽，排除名次。不是一般性，我們假設(shè)他們的名次就是他們?cè)谛〗M中的編號(hào)，即A組的名次是A1、A2、A3、A4、A5，B組和其它組的名次也是類(lèi)似(如下圖)
第二步：讓各組的第一名，也就是A1、B1、C1、D1、E1再比一次，上圖中是第一排紅色的，這樣就能決出第一名。由于A(yíng)1是第一名，A2可能也很厲害，只是運(yùn)氣不好，小組賽遇到了A1，當(dāng)A1已經(jīng)獲得冠軍了，他就應(yīng)該作為亞軍的候選。接下來(lái)就是第三步。
A2和另外四個(gè)組的第一名競(jìng)爭(zhēng)亞軍。如果這一次A2贏(yíng)了，他顯然是亞軍，就由A3遞進(jìn)參加爭(zhēng)奪第三名的比賽。我在下圖中用紅色圈定了這種情況下參加第八次比賽的五位選手。如果A2沒(méi)有贏(yíng)，另四組的某個(gè)第一名贏(yíng)了，哪個(gè)贏(yíng)的人是亞軍，就由那個(gè)組下一位選手遞進(jìn)，角逐第三名。
第四步，如上圖選出五個(gè)人進(jìn)行第三名比賽，致辭，前三名全部產(chǎn)生。但是這個(gè)答案并不完美。最好的答案是什么呢？
其實(shí)前六次比賽是必須的，但是上述方案中有一個(gè)信息忽略了，就是第六組比賽之后（即五個(gè)第一名的比賽）結(jié)束之后，最后的兩名已經(jīng)沒(méi)有資格角逐前三名了。我們假設(shè)那一次比賽從最快到最慢的結(jié)果是A1、B1、C1、D1、E1。在D1和E1之前已經(jīng)有三名選手了，他們肯定不是前三名。
那么誰(shuí)會(huì)是第二名的候選人呢？根據(jù)錦標(biāo)賽的排序原則，直接輸給第一名的人也就是A組的A2，以及最后附加賽輸給他的B1，僅此兩個(gè)人而已。接下來(lái)我們要問(wèn)，除了A2和B1，誰(shuí)還會(huì)是第三名的候選呢？和A1在某一組比賽的第三名，他們是A3、C1，或者輸給第二名候選人B1的人哪個(gè)人，即B2.
因此，第二、三名的候選人一共只有五個(gè)，即A2、A3、C1，或者輸給第二名候選人B1的那個(gè)即B2。
因此，第二、三名的候選人一共只有五個(gè)，即A2、A3、B1、B2、C1（下圖中紅色的選手），剛好湊一組。第七次，這五個(gè)人再跑一把即可，這樣只需要七次，最佳方法。
