超詳細!詳解一道高頻算法題:數組中的第 K 個最大元素

2021-03-02 算法與數據結構

今天分享的題目來源於 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 參考代碼

//思路 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 參考代碼

//思路 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 參考代碼

//思路 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 參考代碼

//思路 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();
        }
    }
}

相關焦點

  • 【每日一題】643. 子數組最大平均數 I
    各位題友大家好,今天是每日算法題公眾號堅持日更的第 11 天。今天力扣上的每日一題是第 643 題「子數組最大平均數 I」。可以通過每日一題的小程序查看題目詳情:題目大意給定 n 個整數,找出平均數最大且長度為 k 的連續子數組,並輸出該最大平均數。
  • leetcode-347前K個高頻元素
    347前K個高頻元素 https://leetcode-cn.com/problems/top-k-frequent-elements/1、題目描述給定一個非空的整數數組,返回其中出現頻率前 k 高的元素。
  • java數組之完美洗牌算法
    題目來源:此題是去年2013年UC的校招筆試題,看似簡單,按照題目所要排序後的字符串蠻力變化即可,但若要完美的達到題目所要求的時空複雜度,則需要我們花費不小的精力。OK,請看下文詳解,一步步優化。起始序列:a1 a2 a3 a4 b1 b2 b3 b4 數組下標:1 2 3 4 5 6 7 8 最終序列:b1 a1 b2 a2 b3 a3 b4 a4從上面的例子我們能看到,前n個元素中, > 第1個元素a1到了原第2個元素a2的位置,即1->2; > 第2個元素a2到了原第4個元素a4的位置,即
  • 漫畫:美團面試題(TOPK:求第K個最大的元素)
    這個題目的變形很多,比如找 "前 K 個高頻元素"、 "數據流中的第K大元素" 、"最接近原點的 K 個值" 等等等等。第215題:在未排序的數組中找到第 k 個最大的元素。請注意,你需要找的是數組排序後的第 k 個最大的元素,而不是第 k 個不同的元素。
  • 【算法】找出數組中和最大的子數組
    首先先講一下歸併排序和快速排序,這兩個算法相信大家學過數據結構與算法的話都不會陌生,還時常出現在面試中。這兩個算法都有相同的地方,把要排序的列表做了分割,換做算法裡的說法是分治。今天要講的就是分治策略。分治,顧名思義,就是把原問題分開多個子問題,一一解決,最後子問題的解合併就是原問題的解。
  • leetcode-215數組中的第K個最大元素
    215數組中的第K個最大元素 https://leetcode-cn.com/problems/kth-largest-element-in-an-array/1、題目描述在未排序的數組中找到第 k 個最大的元素。
  • 算法練習——數組
    例1:給定數組 nums = [1,1,2], 函數應該返回新的長度 2, 並且原數組 nums 的前兩個元素被修改為 1, 2。你不需要考慮數組中超出新長度後面的元素。例2:給定 nums = [0,0,1,1,1,2,2,3,3,4],函數應該返回新的長度 5, 並且原數組 nums 的前五個元素被修改為 0, 1, 2, 3, 4。你不需要考慮數組中超出新長度後面的元素。
  • ​LeetCode刷題實戰53:最大子序和
    所以,為了提高大家的算法能力,這個公眾號後續每天帶大家做一道算法題,題目就從LeetCode上面選 !題意給定一個整數數組 nums ,找到一個具有最大和的連續子數組(子數組最少包含一個元素),返回其最大和。樣例輸入: [-2,1,-3,4,-1,2,1,-5,4]輸出: 6解釋: 連續子數組 [4,-1,2,1] 的和最大,為 6。
  • LeetCode Top 100 高頻算法題 23. Merge k Sorted Lists
    ,即LeetCode上最高頻的100道求職面試算法題。小編和實驗室同學之前面試找工作,也只刷了劍指offer和這top 100算法題,在實際面試中也遇到了很多LeetCode上的原題。劍指offer算法最優解之前和大家分享了,LeetCode Top 100這100道算法題,每道題小編都刷了很多遍,並且總結了一種最適合面試時手撕算法的最優解法。後續每天和大家分享一道LeetCode top 100高頻算法題,以及小編總結的最優解法。
  • 面試題:無序整數數組中找第 K 大的數
    Sa 中的元素大於等於 X,Sb 中元素小於 X。這時,有兩種可能性:1. Sa中元素的個數小於K,Sa中所有的數和Sb中最大的K-|Sa|個元素(|Sa|指Sa中元素的個數)就是數組S中最大的K個數。2. Sa中元素的個數大於或等於K,則需要返回Sa中最大的K個元素。
  • 341,前 K 個高頻元素
    給定一個非空的整數數組,返回其中出現頻率前 k 高的元素。
  • 八大經典排序算法詳解
    二叉堆有兩種:最大堆和最小堆。大根堆:父結點的鍵值總是大於或等於任何一個子節點的鍵值;小根堆:父結點的鍵值總是小於或等於任何一個子節點的鍵值。二叉堆一般用數組來表示。例如,根節點在數組中的位置是0,第n個位置的子節點分別在2n+1和 2n+2。因此,第0個位置的子節點在1和2,1的子節點在3和4。以此類推。這種存儲方式便於尋找父節點和子節點。
  • 力扣(LeetCode)- 常見的排序算法總結
    如何分析一個排序算法好壞時間複雜度、比較和交換次數、原地排序(空間複雜度為(1))、排序穩定性(相等元素之間的位置先後順序不變)。有序度:是數組中具有有序關係的元素對的個數逆序度:和有序度相反。選擇排序是不穩定排序,所以應用最少。
  • 啊這,被一道找中位數的算法題整不會了…
    讀完本文,你可以去力扣拿下第 295 題「數據流的中位數」,難度 Hard。如果輸入一個數組,讓你求中位數,這個好辦,排個序,如果數組長度是奇數,最中間的一個元素就是中位數,如果數組長度是偶數,最中間兩個元素的平均數作為中位數。
  • 數組(並不只是數組)
    看到 O(log L) 這樣的複雜度,而且還是有序數組,能想到哪個算法嗎?沒錯,就是二分查找!要找中位數,就是要找第 k 大的數(k = (L / 2 + 1),其中L 是上面提到的合併後新數組的長度,當 L 是偶數時,要求第 (L / 2) 大和第 (L / 2 + 1) 大的兩個數)。
  • 詳解連續子數組的最大累乘之動態規劃解法
    這個題目,當然可以用窮舉所有子數組的方法,找出最大值,時間複雜度妥妥地為O(n^2),這顯然不是我們想要的。如何用DP降低到O(n)才是我們的目標,這才是算法的魅力所在,接下來,總結DP求解的思維過程。
  • 14種模式搞定面試算法編程題(PART II)
    好了不廢話啦,今天文章的主題繼續分享上一篇未寫完的部分,14種模式搞定面試算法編程題(PART I)。經過本人之前筆試面試經驗證明確實確實非常非常高頻,一定要十分熟悉。應用場景舉個慄子10、Two heaps在許多問題中,給出了一系列元素,需要我們將其分成兩部分。為了解決這個問題,我們想要知道一個部分中的最小元素和另一個部分中的最大元素。
  • 啊這,一道找中位數的算法題把東哥整不會了…
    如果輸入一個數組,讓你求中位數,這個好辦,排個序,如果數組長度是奇數,最中間的一個元素就是中位數,如果數組長度是偶數,最中間兩個元素的平均數作為中位數。如果數據規模非常巨大,排序不太現實,那麼也可以使用概率算法,隨機抽取一部分數據,排序,求中位數,近似作為所有數據的中位數。
  • 洗牌算法:給數組隨機排序
    舉例來說,我們有一個如下圖所示的數組,數組長度為9,數組內元素的值順次分別是 1~9:從上面這個數組入手,我們要做的就是打亂數組內元素的順序:此外,我們將該方法掛載在了 Array對象的原型下面,所以任何數組都可以直接調用該方法:var tempArray = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]tempArray.shuffle(); 工作原理看完代碼之後,讓我們看看它對數組都做了寫什麼。首先,該方法選中數組的最後一個元素:
  • 【面試錦囊】14種模式搞定面試算法編程題(8-14)
    好了不廢話啦,今天文章的主題繼續分享上一篇未寫完的部分,14種模式搞定面試算法編程題(PART I)。經過本人之前筆試面試經驗證明確實確實非常非常高頻,一定要十分熟悉。應用場景舉個慄子10、Two heaps在許多問題中,給出了一系列元素,需要我們將其分成兩部分。為了解決這個問題,我們想要知道一個部分中的最小元素和另一個部分中的最大元素。