LeetCode算法题-Kth Largest Element

作者: 程序员小川 | 来源:发表于2019-04-03 20:24 被阅读5次

    这是悦乐书的第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<Integer> q;
        public KthLargest(int k, int[] nums) {
            this.k = k;
            q = new PriorityQueue<Integer>(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+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

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

    相关文章

      网友评论

        本文标题:LeetCode算法题-Kth Largest Element

        本文链接:https://www.haomeiwen.com/subject/nodtiqtx.html