求n個數中第二小的數的最少需要多少次比較？

02-13

n+㏒n-2次，但實現方法不太明白，求大神指點，謝謝！

錦標賽的方法，這是一種分治的思想。

先從最簡單的找最小數談起。

對於從N個數中找到最小數，比較容易理解必須比較N-1次，才能知道某數是最小的。

在這裡其實有一個隱含信息，最小數和第二小數必然已經比較過了。

所以想繼續找到第二小的數，可以縮小第二次查找的範圍，僅僅從已經和最小數比較過的集合A里進行查找。那麼如何才能儘可能的縮小集合A的大小呢？——分治。

對數組a[1…n]中元素成對的做比較，每次比較後將較小的數拿出，形成新的數組再繼續這樣處理，直到剩下最後的一個，就是數組中最小的那個。將比較的過程以一個樹的形式表現出來，如下圖：

樹中藍色的節點就是和最小數1比較過的節點，我們可以發現每層只存在一次比較，因此如上文所述的集合A的最小值為 樹的深度-1 即 logN-1.

通過空間換時間的方式，將每個數比較過的數以鏈表的方式存儲下來，這個鏈表後邊的值也就是集合A了。如下圖：

所以最終的最少比較次數為 (N - 1) + (logN -1) = N + logN - 2. (左括弧是找最小所需次數，右邊括弧里是找第二小所需的次數）

首先我們證明這個下界是可以得到的。

對於n個輸入，進行如下操作：

我們將他兩兩配對進行一次比較，每個配對的勝者放入等待隊列；
如果出現未配對的數，放入等待隊列；
對等待隊列當作新的輸入，跳轉到1，遞歸執行，直到輸入大小為1

此時剩下的數為最大數，整個比較過程可以看作一個只有0度和2度節點的勝者樹，葉子節點就是原始的輸入，頭節點就是最後的最大值，每個2度節點都代表一次比較。根據這種只有0度和2度節點樹的特性，內部節點剛好有n-1個，所以獲得最大值需要n-1次操作。

現在我們來獲得第二大的數，這個數有一個性質：他一定與最大數比較過，且是所有與最大數比較過的數中的最大數。為了得到第二大的數，我們只需要收集最大數在整棵勝者樹中路徑所有的兄弟節點，並在此調用一次最大數演算法，即可得到第二大的數。由於當前勝者樹的形狀，最大數的所有兄弟節點個數不會超過 $lceil lgn ceil$ ,所以得到第二大數的比較次數不會超過 $lceil lgn ceil -1$ 。因此，我們可以在 $n+lceil lgn ceil -2$ 比較內得到第二大的數。

現在我們來證明最少需要 $n+lceil lgn ceil -2$ 次比較才能得到第二大的數。

為了得到第二大的數，我們首先需要得到最大的數，然後將所有與最大數比較過的數中找到最大值，即是第二大。為了得到最小比較次數，所有在比較過程中已經輸過的數沒有必要再參加比較。整個選取最大數的過程也是一個勝者樹，這棵樹有2n-1個節點。這棵勝者樹中，任何一條從葉子節點到頭節點的路徑都可能是最大數的比較路徑，最壞情況下，第二大數的候選集合大小為最長路徑長度-1，額外的比較次數為最長路徑長度-2，此時.對於任何一個含有k個節點的二叉樹，其最長路徑至少為 $lceil lg(k+1) ceil$ ，所以勝者樹中最長路徑最短長度為 $lceil lg(2n) ceil=lceil lg(n) ceil +1$ ,所以第二大數的候選集合大小在任何情況下都不可能低於 $lceil lg(n) ceil$ 。因此獲得第二大數所需比較次數最少為 $n-1 +lceil lg(n) ceil -1=n+lceil lg(n) ceil -2$ .

綜上，獲得第二大數所需比較次數的下界即為 $n+lceil lg(n) ceil -2$ 。

組織比賽的人早就想過這個問題了.

所以他們發明了一種玩法叫做雙敗淘汰制.

最後一輪的贏家一定是最小的,輸家一定是第二小的.

N個數兩兩比較，小的放入新數組中，若有剩下的也加入新數組中，然後將新數組重複上述過程，直到數組大小為2，這個過程其實不僅可以找到第二小的，還能找到第一小的喔