今天分享的題目來源于 LeetCode 第 215 號問題，是面試中的高頻考題。

題目描述

在 未排序 的數(shù)組中找到第 k 個最大的元素。請注意，你需要找的是數(shù)組排序后的第 k 個最大的元素，而不是第 k 個不同的元素。

示例 1:

輸入:[3,2,1,5,6,4]和k=2 輸出:5

示例 2:

輸入:[3,2,3,1,2,4,5,5,6]和k=4 輸出:4

說明:

你可以假設 k 總是有效的，且 1 ≤ k ≤ 數(shù)組的長度。

題目解析

方法一：返回升序排序以后索引為 len - k 的元素

題目已經(jīng)告訴你了：

你需要找的是數(shù)組排序后的第 k 個最大的元素，而不是第 k 個不同的元素。

因此，升序排序以后，返回索引為 len - k 這個元素即可。

這是最簡單的思路，如果只答這個方法，可能面試官并不會滿意，但是在我們平時的開發(fā)工作中，還是不能忽視這種思路簡單的方法，我認為理由如下：

1、最簡單同時也一定是最容易編碼的，編碼成功的幾率最高，可以用這個最簡單思路編碼的結(jié)果和其它思路編碼的結(jié)果進行比對，驗證高級算法的正確性；

2、在數(shù)據(jù)規(guī)模小、對時間復雜度、空間復雜度要求不高的時候，真沒必要上 “高大上” 的算法；

3、思路簡單的算法考慮清楚了，有些時候能為實現(xiàn)高級算法鋪路。這道題正是如此，“數(shù)組排序后的第 k 個最大的元素” ，語義是從右邊往左邊數(shù)第 k 個元素（從 1 開始），那么從左向右數(shù)是第幾個呢，我們列出幾個找找規(guī)律就好了。

一共 6 個元素，找第 2 大，索引是 4；
一共 6 個元素，找第 4 大，索引是 2。

因此，目標元素的索引是 len - k，即找最終排定以后位于 len - k 的那個元素；

4、低級算法往往容錯性最好，即在輸入不滿足題目條件的時候，往往還能得到正確的答案，而高級算法對輸入數(shù)據(jù)的要求就非常苛刻。

參考代碼

importjava.util.Arrays; publicclassSolution{ publicintfindKthLargest(int[]nums,intk){ intlen=nums.length; Arrays.sort(nums); returnnums[len-k]; } }

復雜度分析

時間復雜度：O(NlogN)。這里 N 是數(shù)組的長度，算法的性能消耗主要在排序，JDK 默認使用快速排序，因此時間復雜度為O(NlogN)。

空間復雜度：O(1)。這里是原地排序，沒有借助額外的輔助空間。

到這里，我們已經(jīng)分析出了：

1、我們應該返回最終排定以后位于 len - k 的那個元素；
2、性能消耗主要在排序，JDK 默認使用快速排序。

學習過 “快速排序” 的朋友，一定知道一個操作叫 partition，它是 “分而治之” 思想當中 “分” 的那一步。

經(jīng)過 partition 操作以后，每一次都能排定一個元素，并且這個元素左邊的數(shù)都不大于它，這個元素右邊的數(shù)都不小于它，并且我們還能知道排定以后的元素的索引。

于是可以應用 “減而治之”（分治思想的特例）的思想，把問題規(guī)模轉(zhuǎn)化到一個更小的范圍里。

于是得到方法二。

方法二：借助 partition 操作定位

方法二則是借助 partition 操作定位到最終排定以后索引為 len - k 的那個元素。

以下的描述基于 “快速排序” 算法知識的學習，如果忘記的朋友們可以翻一翻自己的《數(shù)據(jù)結(jié)構(gòu)與算法》教材，復習一下，partition 過程、分治思想和 “快速排序” 算法的優(yōu)化。

【圖解數(shù)據(jù)結(jié)構(gòu)】 一組動畫徹底理解快速排序

我們在學習 “快速排序” 的時候，接觸的第 1 個操作就是 partition（切分），簡單介紹如下：

partition（切分）操作，使得：

對于某個索引 j，nums[j] 已經(jīng)排定，即 nums[j] 經(jīng)過 partition（切分）操作以后會放置在它 “最終應該放置的地方”；

nums[left] 到 nums[j - 1] 中的所有元素都不大于 nums[j]；

nums[j + 1] 到 nums[right] 中的所有元素都不小于 nums[j]。

partition（切分）操作總能排定一個元素，還能夠知道這個元素它最終所在的位置，這樣每經(jīng)過一次 partition操作就能縮小搜索的范圍，這樣的額思想叫做 “減而治之”（是 “分而治之” 思想的特例）。

切分過程可以不借助額外的數(shù)組空間，僅通過交換數(shù)組元素實現(xiàn)。下面是參考代碼：

參考代碼

publicclassSolution{ publicintfindKthLargest(int[]nums,intk){ intlen=nums.length; intleft=0; intright=len-1; //轉(zhuǎn)換一下，第k大元素的索引是len-k inttarget=len-k; while(true){ intindex=partition(nums,left,right); if(index==target){ returnnums[index]; }elseif(indextarget; right=index-1; } } } /** *在nums數(shù)組的[left,right]部分執(zhí)行partition操作，返回nums[i]排序以后應該在的位置 *在遍歷過程中保持循環(huán)不變量的語義 *1、(left,k]=nums[left] * *@paramnums *@paramleft *@paramright *@return */ publicintpartition(int[]nums,intleft,intright){ intpivot=nums[left]; intj=left; for(inti=left+1;i<=?right;?i++)?{ ????????????if?(nums[i]?

復雜度分析

時間復雜度：O(N)。這里 N 是數(shù)組的長度。

空間復雜度：O(1)。這里是原地排序，沒有借助額外的輔助空間。

方法三：優(yōu)先隊列

優(yōu)先隊列的寫法就很多了，這里例舉一下我能想到的。

假設數(shù)組有 len 個元素。

思路 1 ：把 len 個元素都放入一個最小堆中，然后再 pop() 出 len - k 個元素，此時最小堆只剩下 k 個元素，堆頂元素就是數(shù)組中的第 k 個最大元素。

思路 2 ：把 len 個元素都放入一個最大堆中，然后再 pop() 出 k - 1 個元素，因為前 k - 1 大的元素都被彈出了，此時最大堆的堆頂元素就是數(shù)組中的第 k 個最大元素。

思路 3 ：只用 k 個容量的優(yōu)先隊列，而不用全部 len 個容量。

思路 4：用 k + 1 個容量的優(yōu)先隊列，使得上面的過程更“連貫”一些，到了 k 個以后的元素，就進來一個，出去一個，讓優(yōu)先隊列自己去維護大小關(guān)系。

思路 5：綜合考慮以上兩種情況，總之都是為了節(jié)約空間復雜度。即 k 較小的時候使用最小堆，k 較大的時候使用最大堆。

根據(jù)以上思路，分別寫出下面的代碼：

思路 1 參考代碼

//思路 1 ：把`len`個元素都放入一個最小堆中，然后再 pop()出 len - k 個元素，此時最小堆只剩下`k`個元素，堆頂元素就是數(shù)組中的第`k`個最大元素。 importjava.util.PriorityQueue; publicclassSolution{ publicintfindKthLargest(int[]nums,intk){ intlen=nums.length; //使用一個含有 len 個元素的最小堆，默認是最小堆，可以不寫 lambda 表達式：(a, b)-> a - b PriorityQueueminHeap=newPriorityQueue<>(len,(a,b)->a-b); for(inti=0;i

思路 2 參考代碼

//思路 2 ：把`len`個元素都放入一個最大堆中，然后再 pop()出 k - 1 個元素，因為前 k - 1 大的元素都被彈出了，此時最大堆的堆頂元素就是數(shù)組中的第`k`個最大元素。 importjava.util.PriorityQueue; publicclassSolution{ publicintfindKthLargest(int[]nums,intk){ intlen=nums.length; //使用一個含有 len 個元素的最大堆，lambda 表達式應寫成：(a, b)-> b - a PriorityQueuemaxHeap=newPriorityQueue<>(len,(a,b)->b-a); for(inti=0;i

思路 3 參考代碼

//思路 3 ：只用`k`個容量的優(yōu)先隊列，而不用全部`len`個容量。 importjava.util.PriorityQueue; publicclassSolution{ publicintfindKthLargest(int[]nums,intk){ intlen=nums.length; //使用一個含有k個元素的最小堆 PriorityQueueminHeap=newPriorityQueue<>(k,(a,b)->a-b); for(inti=0;itopEle){ minHeap.poll(); minHeap.add(nums[i]); } } returnminHeap.peek(); } }

思路 4 參考代碼

//思路 4：用`k + 1`個容量的優(yōu)先隊列，使得上面的過程更“連貫”一些，到了`k`個以后的元素，就進來一個，出去一個，讓優(yōu)先隊列自己去維護大小關(guān)系。 importjava.util.PriorityQueue; publicclassSolution{ publicintfindKthLargest(int[]nums,intk){ intlen=nums.length; //最小堆 PriorityQueuepriorityQueue=newPriorityQueue<>(k+1,(a,b)->(a-b)); for(inti=0;i

思路 5 參考代碼

//思路 5：綜合考慮以上兩種情況，總之都是為了節(jié)約空間復雜度。即`k`較小的時候使用最小堆，`k`較大的時候使用最大堆。 importjava.util.PriorityQueue; publicclassSolution{ //根據(jù)k的不同，選最大堆和最小堆，目的是讓堆中的元素更小 //思路 1：k 要是更靠近0的話，此時 k 是一個較大的數(shù)，用最大堆 //例如在一個有6個元素的數(shù)組里找第5大的元素 //思路 2：k 要是更靠近 len 的話，用最小堆 //所以分界點就是k=len-k publicintfindKthLargest(int[]nums,intk){ intlen=nums.length; if(k<=?len?-?k)?{ ????????????//?System.out.println("使用最小堆"); ????????????//?特例：k = 1，用容量為 k 的最小堆 ????????????//?使用一個含有?k?個元素的最小堆 ????????????PriorityQueueminHeap=newPriorityQueue<>(k,(a,b)->a-b); for(inti=0;itopEle){ minHeap.poll(); minHeap.add(nums[i]); } } returnminHeap.peek(); }else{ //System.out.println("使用最大堆"); assertk>len-k; //特例：k = 100，用容量為 len - k + 1 的最大堆 intcapacity=len-k+1; PriorityQueuemaxHeap=newPriorityQueue<>(capacity,(a,b)->b-a); for(inti=0;i