这是悦乐书的第296次更新，第315篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第164题（顺位题号是703）。设计一个类来查找流中第k个最大元素。请注意，它是排序顺序中的第k个最大元素，而不是第k个不同元素。KthLargest类有一个构造方法，此构造方法有一个整数k和一个整数数组nums两个参数，它包含来自流的初始元素。对于方法KthLargest.add的每次调用，返回表示流中第k个最大元素的元素。例如：

int k = 3;

int [] arr = [4,5,8,2];

KthLargest kthLargest = new KthLargest（3，arr）;

kthLargest.add（3）; //返回4

kthLargest.add（5）; //返回5

kthLargest.add（10）; //返回5

kthLargest.add（9）; //返回8

kthLargest.add（4）; //返回8

注意：nums的长度大于等于0。

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 第一种解法

直接解法。使用数组，在add方法里，首先将原数组扩容，将新的元素添加进数组中去，再对数组排序，然后取出倒数第k个元素。期间，借助工具类Arrays来实现数组扩容和排序。

class KthLargest {    int k;    int[] nums;    public KthLargest(int k, int[] nums) {        this.k = k;        this.nums = nums;    }    public int add(int val) {        int[] temp = Arrays.copyOf(nums, nums.length+1);        temp[temp.length-1] = val;        Arrays.sort(temp);        nums = temp;        return temp[nums.length-k];    }}/** * Your KthLargest object will be instantiated and called as such: * KthLargest obj = new KthLargest(k, nums); * int param_1 = obj.add(val); */

03 第二种解法

使用优先队列。优先队列自带排序算法，在初始化时如果不指定排序方式，则默认以自然方式排序，优先队列的头就会是以自然排序为基础的最小元素。因此，我们可以在初始化优先队列时，就指定其大小为k，然后找出最大的前k个元素存入优先队列，每次调用add方法时，就比较传参val和队列头的大小，如果val比队列头大，就移除原队列头，将val作为新的队列头。

class KthLargest {    int k;    PriorityQueue
    
      q;    public KthLargest(int k, int[] nums) {        this.k = k;        q = new PriorityQueue
     
      (k);        for (int n : nums) {            add(n);        }    }    public int add(int val) {        if (q.size() < k) {            q.offer(val);        } else if (q.peek() < val) {            q.poll();            q.offer(val);        }        return q.peek();    }}/** * Your KthLargest object will be instantiated and called as such: * KthLargest obj = new KthLargest(k, nums); * int param_1 = obj.add(val); */
     
    

04 小结

算法专题目前已日更超过四个月，算法题文章164+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！