詳解一道高頻算法題：數(shù)組中的第 K 個(gè)最大元素

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

題目描述

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

示例 1:

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

示例 2:

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

說明:

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

題目解析

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

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

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

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

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

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

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

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

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

因此，目標(biāo)元素的索引是 len - k，即找最終排定以后位于 len - k 的那個(gè)元素；

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

參考代碼

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

復(fù)雜度分析

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

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

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

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

學(xué)習(xí)過 “快速排序” 的朋友，一定知道一個(gè)操作叫 partition，它是 “分而治之” 思想當(dāng)中 “分” 的那一步。

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

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

于是得到方法二。

方法二：借助 partition 操作定位

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

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

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

我們?cè)趯W(xué)習(xí) “快速排序” 的時(shí)候，接觸的第 1 個(gè)操作就是 partition（切分），簡(jiǎn)單介紹如下：

partition（切分）操作，使得：

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

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

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

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

切分過程可以不借助額外的數(shù)組空間，僅通過交換數(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]排序以后應(yīng)該在的位置 *在遍歷過程中保持循環(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]?

復(fù)雜度分析

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

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

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

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

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

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

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

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

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

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

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

思路 1 參考代碼

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

思路 2 參考代碼

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

思路 3 參考代碼

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

思路 4 參考代碼

//思路 4：用`k + 1`個(gè)容量的優(yōu)先隊(duì)列，使得上面的過程更“連貫”一些，到了`k`個(gè)以后的元素，就進(jìn)來一個(gè)，出去一個(gè)，讓優(yōu)先隊(duì)列自己去維護(hù)大小關(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é)約空間復(fù)雜度。即`k`較小的時(shí)候使用最小堆，`k`較大的時(shí)候使用最大堆。 importjava.util.PriorityQueue; publicclassSolution{ //根據(jù)k的不同，選最大堆和最小堆，目的是讓堆中的元素更小 //思路 1：k 要是更靠近0的話，此時(shí) k 是一個(gè)較大的數(shù)，用最大堆 //例如在一個(gè)有6個(gè)元素的數(shù)組里找第5大的元素 //思路 2：k 要是更靠近 len 的話，用最小堆 //所以分界點(diǎn)就是k=len-k publicintfindKthLargest(int[]nums,intk){ intlen=nums.length; if(k<=?len?-?k)?{ ????????????//?System.out.println("使用最小堆"); ????????????//?特例：k = 1，用容量為 k 的最小堆 ????????????//?使用一個(gè)含有?k?個(gè)元素的最小堆 ????????????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