本文共 1034 字,大约阅读时间需要 3 分钟。
设计一个找到数据流中第 k 大元素的类(class)。注意是排序后的第 k 大元素,不是第 k 个不同的元素。
请实现 KthLargest 类:
KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。 int add(int val) 返回当前数据流中第 k 大的元素。
示例:
输入:
[“KthLargest”, “add”, “add”, “add”, “add”, “add”] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]] 输出: [null, 4, 5, 5, 8, 8]
解释:
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]); kthLargest.add(3); // return 4 kthLargest.add(5); // return 5 kthLargest.add(10); // return 5 kthLargest.add(9); // return 8 kthLargest.add(4); // return 8
用优先级队列构建一个小顶堆,然后再add即可
package com.lcz.leetcode;/** * 数据流中第K大元素 * @author LvChaoZhang * */import java.util.*;public class Leetcode703 { class KthLargest{ // 优先级队列 private PriorityQueuequeue; int limit; public KthLargest(int k,int[] nums) { limit = k; queue = new PriorityQueue<>(k); for(int num:nums) { // 调用下面的函数 add(num); } } public int add(int val) { if(queue.size() queue.peek()) { queue.poll(); queue.offer(val); } return queue.peek(); } }}
转载地址:http://rwwdf.baihongyu.com/