今天分享的題目來源於 LeetCode 第 215 號問題,是面試中的高頻考題。
在 未排序 的數組中找到第 k 個最大的元素。請注意,你需要找的是數組排序後的第 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 ≤ 數組的長度。
方法一:返回升序排序以後索引為 len - k 的元素題目已經告訴你了:
你需要找的是數組排序後的第 k 個最大的元素,而不是第 k 個不同的元素。
因此,升序排序以後,返回索引為 len - k 這個元素即可。
這是最簡單的思路,如果只答這個方法,可能面試官並不會滿意,但是在我們平時的開發工作中,還是不能忽視這種思路簡單的方法,我認為理由如下:
1、最簡單同時也一定是最容易編碼的,編碼成功的機率最高,可以用這個最簡單思路編碼的結果和其它思路編碼的結果進行比對,驗證高級算法的正確性;
2、在數據規模小、對時間複雜度、空間複雜度要求不高的時候,真沒必要上 「高大上」 的算法;
3、思路簡單的算法考慮清楚了,有些時候能為實現高級算法鋪路。這道題正是如此,「數組排序後的第 k 個最大的元素」 ,語義是從右邊往左邊數第 k 個元素(從 1 開始),那麼從左向右數是第幾個呢,我們列出幾個找找規律就好了。
一共 6 個元素,找第 2 大,索引是 4;
一共 6 個元素,找第 4 大,索引是 2。
因此,目標元素的索引是 len - k,即找最終排定以後位於 len - k 的那個元素;
4、低級算法往往容錯性最好,即在輸入不滿足題目條件的時候,往往還能得到正確的答案,而高級算法對輸入數據的要求就非常苛刻。
參考代碼import java.util.Arrays;
public class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
Arrays.sort(nums);
return nums[len - k];
}
}
到這裡,我們已經分析出了:
1、我們應該返回最終排定以後位於 len - k 的那個元素;
2、性能消耗主要在排序,JDK 默認使用快速排序。
學習過 「快速排序」 的朋友,一定知道一個操作叫 partition,它是 「分而治之」 思想當中 「分」 的那一步。
經過 partition 操作以後,每一次都能排定一個元素,並且這個元素左邊的數都不大於它,這個元素右邊的數都不小於它,並且我們還能知道排定以後的元素的索引。
於是可以應用 「減而治之」(分治思想的特例)的思想,把問題規模轉化到一個更小的範圍裡。
於是得到方法二。
方法二:藉助 partition 操作定位方法二則是藉助 partition 操作定位到最終排定以後索引為 len - k 的那個元素。
以下的描述基於 「快速排序」 算法知識的學習,如果忘記的朋友們可以翻一翻自己的《數據結構與算法》教材,複習一下,partition 過程、分治思想和 「快速排序」 算法的優化。
【圖解數據結構】 一組動畫徹底理解快速排序
我們在學習 「快速排序」 的時候,接觸的第 1 個操作就是 partition(切分),簡單介紹如下:
partition(切分)操作,使得:
對於某個索引 j,nums[j] 已經排定,即 nums[j] 經過 partition(切分)操作以後會放置在它 「最終應該放置的地方」;
nums[left] 到 nums[j - 1] 中的所有元素都不大於 nums[j];
nums[j + 1] 到 nums[right] 中的所有元素都不小於 nums[j]。
partition(切分)操作總能排定一個元素,還能夠知道這個元素它最終所在的位置,這樣每經過一次 partition操作就能縮小搜索的範圍,這樣的額思想叫做 「減而治之」(是 「分而治之」 思想的特例)。
切分過程可以不藉助額外的數組空間,僅通過交換數組元素實現。下面是參考代碼:
參考代碼public class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
int left = 0;
int right = len - 1;
// 轉換一下,第 k 大元素的索引是 len - k
int target = len - k;
while (true) {
int index = partition(nums, left, right);
if (index == target) {
return nums[index];
} else if (index < target) {
left = index + 1;
} else {
assert index > target;
right = index - 1;
}
}
}
/**
* 在 nums 數組的 [left, right] 部分執行 partition 操作,返回 nums[i] 排序以後應該在的位置
* 在遍歷過程中保持循環不變量的語義
* 1、(left, k] < nums[left]
* 2、(k, i] >= nums[left]
*
* @param nums
* @param left
* @param right
* @return
*/
public int partition(int[] nums, int left, int right) {
int pivot = nums[left];
int j = left;
for (int i = left + 1; i <= right; i++) {
if (nums[i] < pivot) {
// 小於 pivot 的元素都被交換到前面
j++;
swap(nums, j, i);
}
}
// 最後這一步不要忘記了
swap(nums, j, left);
return j;
}
private void swap(int[] nums, int index1, int index2) {
if (index1 == index2) {
return;
}
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
}
優先隊列的寫法就很多了,這裡例舉一下我能想到的。
假設數組有 len 個元素。
思路 1 :把 len 個元素都放入一個最小堆中,然後再 pop() 出 len - k 個元素,此時最小堆只剩下 k 個元素,堆頂元素就是數組中的第 k 個最大元素。
思路 2 :把 len 個元素都放入一個最大堆中,然後再 pop() 出 k - 1 個元素,因為前 k - 1 大的元素都被彈出了,此時最大堆的堆頂元素就是數組中的第 k 個最大元素。
思路 3 :只用 k 個容量的優先隊列,而不用全部 len 個容量。
思路 4:用 k + 1 個容量的優先隊列,使得上面的過程更「連貫」一些,到了 k 個以後的元素,就進來一個,出去一個,讓優先隊列自己去維護大小關係。
思路 5:綜合考慮以上兩種情況,總之都是為了節約空間複雜度。即 k 較小的時候使用最小堆,k 較大的時候使用最大堆。
根據以上思路,分別寫出下面的代碼:
思路 1 參考代碼//思路 1 :把 `len` 個元素都放入一個最小堆中,然後再 pop() 出 len - k 個元素,此時最小堆只剩下 `k` 個元素,堆頂元素就是數組中的第 `k` 個最大元素。
import java.util.PriorityQueue;
public class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
// 使用一個含有 len 個元素的最小堆,默認是最小堆,可以不寫 lambda 表達式:(a, b) -> a - b
PriorityQueue<Integer> minHeap = new PriorityQueue<>(len, (a, b) -> a - b);
for (int i = 0; i < len; i++) {
minHeap.add(nums[i]);
}
for (int i = 0; i < len - k; i++) {
minHeap.poll();
}
return minHeap.peek();
}
}
//思路 2 :把 `len` 個元素都放入一個最大堆中,然後再 pop() 出 k - 1 個元素,因為前 k - 1 大的元素都被彈出了,此時最大堆的堆頂元素就是數組中的第 `k` 個最大元素。
import java.util.PriorityQueue;
public class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
// 使用一個含有 len 個元素的最大堆,lambda 表達式應寫成:(a, b) -> b - a
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(len, (a, b) -> b - a);
for (int i = 0; i < len; i++) {
maxHeap.add(nums[i]);
}
for (int i = 0; i < k - 1; i++) {
maxHeap.poll();
}
return maxHeap.peek();
}
}
//思路 3 :只用 `k` 個容量的優先隊列,而不用全部 `len` 個容量。
import java.util.PriorityQueue;
public class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
// 使用一個含有 k 個元素的最小堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> a - b);
for (int i = 0; i < k; i++) {
minHeap.add(nums[i]);
}
for (int i = k; i < len; i++) {
// 看一眼,不拿出,因為有可能沒有必要替換
Integer topEle = minHeap.peek();
// 只要當前遍歷的元素比堆頂元素大,堆頂彈出,遍歷的元素進去
if (nums[i] > topEle) {
minHeap.poll();
minHeap.add(nums[i]);
}
}
return minHeap.peek();
}
}
//思路 4:用 `k + 1` 個容量的優先隊列,使得上面的過程更「連貫」一些,到了 `k` 個以後的元素,就進來一個,出去一個,讓優先隊列自己去維護大小關係。
import java.util.PriorityQueue;
public class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
// 最小堆
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k + 1, (a, b) -> (a - b));
for (int i = 0; i < k; i++) {
priorityQueue.add(nums[i]);
}
for (int i = k; i < len; i++) {
priorityQueue.add(nums[i]);
priorityQueue.poll();
}
return priorityQueue.peek();
}
}
//思路 5:綜合考慮以上兩種情況,總之都是為了節約空間複雜度。即 `k` 較小的時候使用最小堆,`k` 較大的時候使用最大堆。
import java.util.PriorityQueue;
public class Solution {
// 根據 k 的不同,選最大堆和最小堆,目的是讓堆中的元素更小
// 思路 1:k 要是更靠近 0 的話,此時 k 是一個較大的數,用最大堆
// 例如在一個有 6 個元素的數組裡找第 5 大的元素
// 思路 2:k 要是更靠近 len 的話,用最小堆
// 所以分界點就是 k = len - k
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
if (k <= len - k) {
// System.out.println("使用最小堆");
// 特例:k = 1,用容量為 k 的最小堆
// 使用一個含有 k 個元素的最小堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> a - b);
for (int i = 0; i < k; i++) {
minHeap.add(nums[i]);
}
for (int i = k; i < len; i++) {
// 看一眼,不拿出,因為有可能沒有必要替換
Integer topEle = minHeap.peek();
// 只要當前遍歷的元素比堆頂元素大,堆頂彈出,遍歷的元素進去
if (nums[i] > topEle) {
minHeap.poll();
minHeap.add(nums[i]);
}
}
return minHeap.peek();
} else {
// System.out.println("使用最大堆");
assert k > len - k;
// 特例:k = 100,用容量為 len - k + 1 的最大堆
int capacity = len - k + 1;
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(capacity, (a, b) -> b - a);
for (int i = 0; i < capacity; i++) {
maxHeap.add(nums[i]);
}
for (int i = capacity; i < len; i++) {
// 看一眼,不拿出,因為有可能沒有必要替換
Integer topEle = maxHeap.peek();
// 只要當前遍歷的元素比堆頂元素大,堆頂彈出,遍歷的元素進去
if (nums[i] < topEle) {
maxHeap.poll();
maxHeap.add(nums[i]);
}
}
return maxHeap.peek();
}
}
}