【面試高頻題】難度 1.5/5，多解法經典面試題

題目描述

這是 LeetCode 上的 ​​215. 數組中的第K個最大元素​​ ，難度為 中等。

Tag : 「樹狀數組」、「二分」、「優先隊列（堆）」、「快速選擇」

給定整數數組 ​

​nums​

​​ 和整數 ​

​k​

​​，請傳回數組中第 ​

​k​

​ 個最大的元素。

請注意，你需要找的是數組排序後的第 ​

​k​

​​ 個最大的元素，而不是第 ​

​k​

​ 個不同的元素。

你必須設計并實作時間複雜度為

示例 1:

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

示例 2:

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

提示：

值域映射 + 樹狀數組 + 二分

除了直接對數組進行排序，取第 位的

對于值域大小 小于 數組長度本身時，我們還能使用「樹狀數組 + 二分」的 做法，其中

首先值域大小為 ，為了友善，我們為每個 增加大小為 的偏移量，将值域映射到

将每個增加偏移量後的 存入樹狀數組，考慮在 範圍内進行二分，假設我們真實第 大的值為 ，那麼在以

• 在範圍内的數滿足「樹狀數組中大于等于的數不低于
• 在範圍内的數不滿足「樹狀數組中大于等于的數不低于

二分出結果後再減去剛開始添加的偏移量即是答案。

代碼：

class Solution {
    int M = 10010, N = 2 * M;
    int[] tr = new int[N];
    int lowbit(int {
        return x & -x;
    }
    int query(int {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i];
        return ans;
    }
    void add(int {
        for (int i = x; i < N; i += lowbit(i)) tr[i]++;
    }
    public int findKthLargest(int[] nums, int {
        for (int x : nums) add(x + M);
        int l = 0, r = N - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (query(N - 1) - query(mid - 1) >= k) l = mid;
            else r = mid - 1;
        }
        return      

• 時間複雜度：将所有數字放入樹狀數組複雜度為；二分出答案複雜度為，其中為值域大小。整體複雜度為
• 空間複雜度：

優先隊列（堆）

另外一個容易想到的想法是利用優先隊列（堆），由于題目要我們求的是第

根據目前隊列元素個數或目前元素與棧頂元素的大小關系進行分情況讨論：

• 當優先隊列元素不足
• 當優先隊列元素達到

代碼：

class Solution {
    public int findKthLargest(int[] nums, int {
        PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->a-b);
        for (int x : nums) {
            if (q.size() < k || q.peek() < x) q.add(x);
            if (q.size() > k) q.poll();
        }
        return      

• 時間複雜度：
• 空間複雜度：

快速選擇

對于給定數組，求解第

基本思路與「快速排序」一緻，每次敲定一個基準值 ​

​x​

​​，根據目前與 ​

​x​

​​ 的大小關系，将範圍在 的

同時利用，利用題目隻要求輸出第 大的值，而不需要對數組進行整體排序，我們隻需要根據劃分兩邊後，第

快速排序模闆為面試向重點内容，需要重要掌握。

代碼：

class Solution {
    int[] nums;
    int qselect(int l, int r, int {
        if (l == r) return nums[k];
        int x = nums[l], i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (nums[i] < x);
            do j--; while (nums[j] > x);
            if (i < j) swap(i, j);
        }
        if (k <= j) return qselect(l, j, k);
        else return qselect(j + 1, r, k);
    }
    void swap(int i, int {
        int c = nums[i];
        nums[i] = nums[j];
        nums[j] = c;
    }
    public int findKthLargest(int[] _nums, int {
        nums = _nums;
        int n = nums.length;
        return qselect(0, n - 1, n - k);
    }
}      

• 時間複雜度：期望
• 空間複雜度：忽略遞歸帶來的額外空間開銷，複雜度為

最後

這是我們「刷穿 LeetCode」系列文章的第 ​

​No.215​

​ 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。

在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。