703. 數(shù)據(jù)流中的第K大元素

設(shè)計(jì)一個(gè)找到數(shù)據(jù)流中第K大元素的類(lèi)（class）。注意是排序后的第K大元素室叉，不是第K個(gè)不同的元素。

你的 KthLargest 類(lèi)需要一個(gè)同時(shí)接收整數(shù) k 和整數(shù)數(shù)組nums 的構(gòu)造器揪胃，它包含數(shù)據(jù)流中的初始元素艾君。每次調(diào)用 KthLargest.add，返回當(dāng)前數(shù)據(jù)流中第K大的元素吗购。

示例:

int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3);   // returns 4
kthLargest.add(5);   // returns 5
kthLargest.add(10);  // returns 5
kthLargest.add(9);   // returns 8
kthLargest.add(4);   // returns 8

說(shuō)明:

你可以假設(shè) nums 的長(zhǎng)度≥ k-1 且k ≥ 1医男。

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/kth--element-in-a-stream/
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)捻勉，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處镀梭。

• 1. 暴力破解法（超時(shí)）

思路：使用排序思想

1. 創(chuàng)建list，將數(shù)組中所有元素都添加到 list中
2. 對(duì)list進(jìn)行排序
3. 找出 list 中第 K 大的元素

private int k;
    private List<Integer> list;
    public KthLargest(int k, int[] nums) {
        this.k = k;
        list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            add(nums[i]);
        }
    }

    public int add(int val) {
        list.add(val);
        Collections.sort(list);
        return list.get(list.size() < k ? 0 : list.size() - k);
    }

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(n ^ 2), 在遍歷數(shù)組過(guò)程中需要對(duì)list進(jìn)行排序

• 空間復(fù)雜度：O(k), list 所占用的空間大小

• 2. 優(yōu)先隊(duì)列法

該問(wèn)題類(lèi)似于LeetCode 347. 前 K 個(gè)高頻元素 - 簡(jiǎn)書(shū)

思路：這種求第K大元素都可以使用優(yōu)先隊(duì)列(最大堆踱启，最小堆)完成

最大堆

1. 創(chuàng)建一個(gè)優(yōu)先隊(duì)列 PriorityQueue, 在其中添加 K 個(gè)元素
2. 由于該優(yōu)先隊(duì)列實(shí)現(xiàn)是一個(gè)最小堆报账，所以堆頂元素一定是這3個(gè)中的最小值研底，如果要添加的這個(gè)數(shù)大于堆頂元素，那么直接進(jìn)行替換
3. 替換完成之后透罢，這個(gè)優(yōu)先隊(duì)列中一定存儲(chǔ)這數(shù)組中前 K 大的元素榜晦，而我們要找的元素 K 就是堆頂元素

private int k;
    private PriorityQueue<Integer> queue;
    public KthLargest(int k, int[] nums) {
        this.k = k;
        //創(chuàng)建優(yōu)先隊(duì)列, 底層實(shí)現(xiàn)是一個(gè)最小堆
        queue = new PriorityQueue<>();
        for (int i = 0; i < nums.length; i++) {
            add(nums[i]);
        }
    }

    public int add(int val) {
        if (queue.size() < k) {
            queue.offer(val);
        } else {
            if (val > queue.peek()) {
                queue.poll();
                queue.offer(val);
            }
        }
        return queue.peek();
    }

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(n + log(k)), 其中堆中添加元素時(shí)間復(fù)雜度為 O(log(k))

• 空間復(fù)雜度：O(k), 優(yōu)先隊(duì)列中只用存儲(chǔ) K 個(gè)元素

• 測(cè)試用例

public static void main(String[] args) {
         int[] nums = {4, 5, 8, 2};
         System.out.println("nums:" + Arrays.toString(nums));
         KthLargest kthLargest = new KthLargest(3, nums);
         System.out.println("數(shù)據(jù)流中的第K大元素:" +  kthLargest.add(3));
    }

• 結(jié)果

nums:[4, 5, 8, 2]
數(shù)據(jù)流中的第K大元素:4

• 源碼

• 我會(huì)每天更新新的算法，并盡可能?chē)L試不同解法琐凭，如果發(fā)現(xiàn)問(wèn)題請(qǐng)指正

• Github