關(guān)鍵詞：二叉樹
生活中的淘汰錦標賽：在單淘汰的錦標賽中，選手們兩兩比賽，勝者晉級，敗者被淘汰。比如世界乒乓球錦標賽或者大滿貫網(wǎng)球賽就是這么進行的。
這樣一來，就可以把比賽的賽程和結(jié)果對應成一個二叉樹。在樹中每一個選手是二叉樹中的一個葉子結(jié)點，每一場比賽就相當于兩個數(shù)字在比大小，數(shù)字大的選手獲勝進入下一輪，成為樹干上的根。所以，進入到某一輪比賽的選手，其實都是某個子數(shù)干的根結(jié)點。最后的冠軍就是整個二叉樹的根結(jié)點。這種賽制的合理性需要一個假設：A>B, B>C --> 必然有A>C（輸贏的傳遞性）
錦標賽排序法：對所有數(shù)字排序，復雜度是nlogn（和快速排序差不多）。特定的場合，它更快，如果只選第一名，則算法復雜度只有N，若需要選出第二名，則額外增加logn就可以了，對第三名也是如此。這種方法在從N個選手中選出K個選手的事情中特別快
工程中，要比較兩個數(shù)字的大小
第一步：把所有的數(shù)字放到二叉樹的葉子節(jié)點，然后按照錦標賽單淘汰的方式，兩兩比較選出最大
第二步：對于第二大的，從所有被最大的數(shù)字淘汰的數(shù)字中選擇，以此類推選擇對于第三、第四大的數(shù)字
高盛面試題
假定有25名短跑選手比賽競爭金銀銅牌，賽場上有5條賽道，因此一次可以有5個人同時比賽。比賽不及時，只看相應的名次。假如選手的發(fā)揮是穩(wěn)定的，也就是說如果約翰比張三跑的快，張三比凱利跑的快，那么約翰一定比凱利跑得快。最少需要幾組比賽才能決出前3名？
第一步，將25名選手分成5組，每組5人。讓每個組分別比賽，排出各組的名次來，假設他們的名字就是他們在小組中的編號。
第二步，讓各組的第一名，也就是A1、B1、C1、D1、E1再比一次。假設A1在這次比賽中獲勝，這樣我們就知道了第一名。
第三步，A2和另外四個組的第一名競爭亞軍，A2、B1、C1、D1、E1比一次，假設A2這一次贏了，他就是亞軍。如果A2沒有贏，另外4個組的某個第一名贏了，那個贏的人是亞軍，就由那個組下一位選手遞進，角逐第三名
第四步，如上圖通過8次（5 +1 + 1 +1）選出的5人進行第三名的比賽，前3全部產(chǎn)生
更好的答案：
前6次比賽都是必須的，最佳答案的前2步和上述方案中的前2步是相同的。在第6組比賽（即5個第一名的比賽）結(jié)束之后，最后的2名已經(jīng)沒有資格角逐前3名了。
不妨假設那一次比賽從最快到最慢的結(jié)果是A1、B1、C1、D1、E1，在D1和E1之前已經(jīng)有3名選手了，他們肯定不是前3名。
誰還會是第二名的候選呢？根據(jù)錦標賽排序的原則，直接輸給第一名的人，也就是A2，以及最后附加賽輸給他的B1，僅此兩人而已。
誰會是第三名的候選呢？和A1在某一組比賽的第三名，他們是A3、C1，或者輸給第二名候選人B1的人，即B2。
因此，第二、第三名的候選人一共只有5個， A2、A3、B1、B2和C1，剛好湊一組。這樣加上前6次，只需要賽7組，這是最佳方法。
注：來自吳軍老師得到課程
