關(guān)鍵詞：二叉樹
生活中的淘汰錦標(biāo)賽：在單淘汰的錦標(biāo)賽中敛瓷，選手們兩兩比賽，勝者晉級(jí)镰矿，敗者被淘汰。比如世界乒乓球錦標(biāo)賽或者大滿貫網(wǎng)球賽就是這么進(jìn)行的俘种。
這樣一來(lái)秤标，就可以把比賽的賽程和結(jié)果對(duì)應(yīng)成一個(gè)二叉樹绝淡。在樹中每一個(gè)選手是二叉樹中的一個(gè)葉子結(jié)點(diǎn)，每一場(chǎng)比賽就相當(dāng)于兩個(gè)數(shù)字在比大小苍姜，數(shù)字大的選手獲勝進(jìn)入下一輪牢酵，成為樹干上的根。所以衙猪，進(jìn)入到某一輪比賽的選手馍乙，其實(shí)都是某個(gè)子數(shù)干的根結(jié)點(diǎn)。最后的冠軍就是整個(gè)二叉樹的根結(jié)點(diǎn)垫释。這種賽制的合理性需要一個(gè)假設(shè)：A>B, B>C --> 必然有A>C（輸贏的傳遞性）
錦標(biāo)賽排序法：對(duì)所有數(shù)字排序丝格，復(fù)雜度是nlogn（和快速排序差不多）。特定的場(chǎng)合棵譬，它更快显蝌，如果只選第一名，則算法復(fù)雜度只有N订咸，若需要選出第二名曼尊，則額外增加logn就可以了，對(duì)第三名也是如此脏嚷。這種方法在從N個(gè)選手中選出K個(gè)選手的事情中特別快
工程中骆撇，要比較兩個(gè)數(shù)字的大小
第一步：把所有的數(shù)字放到二叉樹的葉子節(jié)點(diǎn)，然后按照錦標(biāo)賽單淘汰的方式父叙，兩兩比較選出最大
第二步：對(duì)于第二大的神郊，從所有被最大的數(shù)字淘汰的數(shù)字中選擇，以此類推選擇對(duì)于第三高每、第四大的數(shù)字
高盛面試題
假定有25名短跑選手比賽競(jìng)爭(zhēng)金銀銅牌屿岂，賽場(chǎng)上有5條賽道，因此一次可以有5個(gè)人同時(shí)比賽鲸匿。比賽不及時(shí)爷怀，只看相應(yīng)的名次。假如選手的發(fā)揮是穩(wěn)定的带欢，也就是說(shuō)如果約翰比張三跑的快运授，張三比凱利跑的快，那么約翰一定比凱利跑得快乔煞。最少需要幾組比賽才能決出前3名吁朦？
第一步，將25名選手分成5組渡贾，每組5人逗宜。讓每個(gè)組分別比賽，排出各組的名次來(lái)，假設(shè)他們的名字就是他們?cè)谛〗M中的編號(hào)纺讲。
第二步擂仍，讓各組的第一名，也就是A1熬甚、B1逢渔、C1、D1乡括、E1再比一次肃廓。假設(shè)A1在這次比賽中獲勝，這樣我們就知道了第一名诲泌。
第三步盲赊，A2和另外四個(gè)組的第一名競(jìng)爭(zhēng)亞軍，A2档礁、B1角钩、C1、D1呻澜、E1比一次递礼，假設(shè)A2這一次贏了，他就是亞軍羹幸。如果A2沒(méi)有贏脊髓，另外4個(gè)組的某個(gè)第一名贏了，那個(gè)贏的人是亞軍栅受，就由那個(gè)組下一位選手遞進(jìn)将硝，角逐第三名
第四步，如上圖通過(guò)8次（5 +1 + 1 +1）選出的5人進(jìn)行第三名的比賽屏镊，前3全部產(chǎn)生
更好的答案：
前6次比賽都是必須的依疼，最佳答案的前2步和上述方案中的前2步是相同的。在第6組比賽（即5個(gè)第一名的比賽）結(jié)束之后而芥，最后的2名已經(jīng)沒(méi)有資格角逐前3名了律罢。
不妨假設(shè)那一次比賽從最快到最慢的結(jié)果是A1、B1棍丐、C1误辑、D1、E1歌逢，在D1和E1之前已經(jīng)有3名選手了巾钉，他們肯定不是前3名。
誰(shuí)還會(huì)是第二名的候選呢秘案？根據(jù)錦標(biāo)賽排序的原則砰苍，直接輸給第一名的人潦匈，也就是A2，以及最后附加賽輸給他的B1赚导，僅此兩人而已历等。
誰(shuí)會(huì)是第三名的候選呢？和A1在某一組比賽的第三名辟癌，他們是A3、C1荐捻，或者輸給第二名候選人B1的人黍少，即B2。
因此处面，第二厂置、第三名的候選人一共只有5個(gè)， A2魂角、A3昵济、B1、B2和C1野揪，剛好湊一組访忿。這樣加上前6次，只需要賽7組斯稳，這是最佳方法海铆。
注：來(lái)自吳軍老師得到課程
