Find the second largest number in an array.
首先，一個(gè)簡(jiǎn)單直觀的想法：兩次遍歷數(shù)組嚼吞，第一次找到最大的數(shù)，然后第二次找到除了最大的這個(gè)數(shù)之外的最大的數(shù)遏暴。如果沒(méi)有重復(fù)的元素枫绅，需要n-1+n-2次比較就能得到結(jié)果。
然而事實(shí)上問(wèn)題的定義是不夠明確的芯砸。在開(kāi)始想解法之前萧芙，至少有以下這些問(wèn)題需要明確
a. 這些數(shù)據(jù)是什么？人的年齡假丧？工資双揪？還是隨機(jī)生成的范圍不確定是一堆數(shù)？
b. 這個(gè)數(shù)組是給定之后就不變的包帚，還是經(jīng)常有增刪操作的渔期？
c. 獲取第二大的數(shù)這個(gè)操作是否經(jīng)常被使用？
d. 需求是否會(huì)變動(dòng)渴邦？比如突然要求找第3大的疯趟，第9大的數(shù)？
如果這些數(shù)是某個(gè)公司的員工號(hào)谋梭，或者員工的年齡呢這樣的元素呢信峻？ 當(dāng)然上面的解法依然可以用。但或許更通用的解法是先把數(shù)組排序瓮床，這樣可以輕松地?cái)U(kuò)展成找第k大的元素的算法：排序盹舞，然后輸出倒數(shù)第k個(gè)元素。
而像人的年齡這樣范圍已知且這個(gè)范圍并不大的數(shù)據(jù)類(lèi)型隘庄，采用諸如基數(shù)排序踢步、計(jì)數(shù)排序這類(lèi)分配式排序算法，時(shí)間復(fù)雜度是O(n)峭沦。如果需要經(jīng)常獲取這個(gè)第二大的數(shù)贾虽，那我們?cè)谇捌诨ㄙM(fèi)一些時(shí)間來(lái)排序，使得此后的操作都是O(1)的吼鱼，這樣整體效率更高蓬豁，何樂(lè)而不為呢？
但如果數(shù)組經(jīng)常被增刪改菇肃，分配式排序就不是那么高效了地粪，因?yàn)橐?jīng)常重新排序。這種情況下堆排序的效率會(huì)更高些：插入或刪除一個(gè)元素的操作都是O(logn)時(shí)間琐谤，而獲得第k大的元素則大致是O(klogn)蟆技。
如果我們的輸入數(shù)據(jù)范圍未知，數(shù)組不可變斗忌，就現(xiàn)在要你給出第二大的數(shù)质礼，怎樣才能使得元素間的比較次數(shù)盡量少呢？
可以采用兩兩比較的錦標(biāo)賽(tournament)策略织阳。就跟遺傳算法里的錦標(biāo)賽選擇策略一樣樣的眶蕉。
這種策略會(huì)形成一種分層比賽的結(jié)構(gòu)，就好像籃球賽唧躲，從小組賽造挽，到四分之一，到半決弄痹，決賽...我們把數(shù)組中元素兩兩分組饭入，比較，優(yōu)勝者進(jìn)入下一輪比賽肛真，再分組谐丢，比賽...直到最后只有一位優(yōu)勝者，這就是最大的數(shù)蚓让。然后第二大的那個(gè)數(shù)之所以沒(méi)有笑到最后庇谆，是因?yàn)樗谀炒伪容^中被干掉了，而能干掉第二大的數(shù)的凭疮，只有這個(gè)最大的數(shù)了饭耳，說(shuō)明最大的數(shù)已經(jīng)和第二大的數(shù)進(jìn)行過(guò)比較了。因此接下來(lái)要做的就是执解，把在每一層比較中被最大數(shù)干掉的那些數(shù)收集起來(lái)寞肖，讓它們?cè)賮?lái)一次這樣逐層的比較，勝出者便是第二大的數(shù)了衰腌。
比如給定的數(shù)組是這樣的：
{4,8,1,3,6,10,7,9,13,2,15,5,16,11,14,12}
分組：{4,8, 1,3, 6,10, 7,9, 13,2, 15,5, 16,11, 14,12}
比較得：{8,3,10,9,13,15,16,14}
分組：{8,3, 10,9, 13,15, 16,14}
比較得{8,10,15,16}
分組:{8,10 ,15,16}
比較得{10, 16}
分組：{ 10,16 }
比較得16新蟆， 為是最大值。這里一共用了8+4+2+1=15=n-1次比較右蕊。
同時(shí)能得到{11,14,15,10}這logn=4個(gè)與16競(jìng)賽時(shí)落敗的數(shù)琼稻。對(duì)它們重復(fù)上述過(guò)程，需要2+1=3=logn -1次比較饶囚。如此便花費(fèi)了n-1+logn-1次比較帕翻，得到數(shù)組中第二大的數(shù)鸠补。
如果像LeetCode#215那樣要求數(shù)組中第k大的數(shù)，可以借鑒快速排序算法中的劃分函數(shù)的思想嘀掸。隨機(jī)選擇一個(gè)劃分參照紫岩，劃分后得到它的位置p，如果p在超過(guò)了第k大的位置睬塌，則把范圍縮小到左邊泉蝌，繼續(xù)找第k大的數(shù)；如果p沒(méi)有超過(guò)第k大的位置揩晴，則把范圍縮小到p的右邊勋陪，找這邊的第k-p+1大的數(shù)。
//java
public int findKthLargest(int[] nums, int k) {
int left=0, right=nums.length-1;
if(left>right || k>nums.length)
return -1;
while(left<right){
int p=partition(nums, left, right);
if(p+1==k)
return nums[p];
else if(p+1>k)
right=p-1;
else
left=p+1;
}
return nums[left];
}
private static int partition(int[] a, int lo, int hi){
int pivot=a[lo];
int i=lo, j=hi+1;
while(true){
while(a[++i]>=pivot && i<hi);
while(a[--j]<=pivot && j>lo);
if(i>=j) break;
swap(a, i, j);
}
swap(a, lo, j);
return j;
}
private static void swap(int[] a, int i, int j){
int tmp=a[i];
a[i]=a[j];
a[j]=tmp;
}
此算法的最差時(shí)間復(fù)雜度是O(n^2)硫兰，而平均時(shí)間復(fù)雜度是O(n)诅愚。證明過(guò)程類(lèi)似快排，略瞄崇。
