超超不会飞

0%

LeetCode703-数据流中第K大元素

Posted on Views: Valine:

题目

设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。

你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器，它包含数据流中的初始元素。每次调用 KthLargest.add，返回当前数据流中第K大的元素。

示例:

1
2
3
4
5
6
7
8
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

分析

题目的意思是说，给一个初始数组，每次往数组中插入一个元素后，返回数组中第K大的元素。

解法一

简化一下题目，先假设要求的是最大值，而不是第K大的值。

我们的思路很简单，遍历初始数组，用一个变量 max 保存数组的最大值。每次插入新的元素，比较是否大于 max ，如果大于，则替换当前 max，如果小于则不做处理。

上面是数据流中求最大值的思路，当我们要求第K大的值时，可以设置一个数组，保存K个最大值，这组元素中最小的值，就是数据流中第K大的元素。每次插入新的元素，比较新插入的元素是否大于数组中的最小值，如果大于，则最小值出队，当前值入队，重新排序该数组。如果小于或等于，则丢弃新插入的元素。

时间复杂度 N*KlogK

空间复杂度 K

解法二

简化解法一。可以使用优先队列（小顶堆）来代替解法一中的数组，可以把排序的时间复杂度降低为 N*logK。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * @author zhangchaohang
 * @date 2020/9/21 08:56
 * leetcode 703 找出第k大的元素
 **/
public class KthLargest {

    /**
     * 优先队列，size与k相同
     */
    private PriorityQueue<Integer> pq;
    private int k;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        this.pq = new PriorityQueue<>(k);
        for (int num : nums) {
            add(num);
        }
    }

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

本文首发于我的个人博客 https://chaohang.top

作者张小超

转载请注明出处

欢迎关注我的微信公众号 【超超不会飞】，获取第一时间的更新。