找出N個數(shù)組中第二大的數(shù)？

從n個數(shù)里面找最大的兩個數(shù)理論最少需要比較的次數(shù)為：n+logn-2解析一：類似比賽晉級，兩兩配對比較，贏的再兩兩配對，最后得到冠軍(最大的數(shù))，可以看成是一棵二叉樹，以4人為例：0020123可以看出，找出最大的數(shù)比較次數(shù)是n-1。然后第二大的數(shù)肯定是跟冠軍比較過的數(shù)字，那么很明顯每一層都有一個，所以有l(wèi)ogn-1次比較。所以總共是n+logn-2次比較。解析二：冒泡法找最大比較次數(shù)為n-1，然后再在之前每一次比較的結(jié)果里面找第二大的數(shù)，比較的次數(shù)為logN，需要減去最后一次最大數(shù)的比較，即求第二個數(shù)是logN-1，結(jié)果就是n+logn-2。