JAVA练习349- 数据流的中位数
题目概览中位数是有序整数列表中的中间值。如果列表的大小是偶数则没有中间值中位数是两个中间值的平均值。例如arr [2,3,4]的中位数是3。例如arr [2,3]的中位数是(2 3) / 2 2.5。实现 MedianFinder 类:MedianFinder()初始化MedianFinder对象。void addNum(int num)将数据流中的整数num添加到数据结构中。double findMedian()返回到目前为止所有元素的中位数。与实际答案相差10-5以内的答案将被接受。示例 1输入[MedianFinder, addNum, addNum, findMedian, addNum, findMedian] [[], [1], [2], [], [3], []]输出[null, null, null, 1.5, null, 2.0]解释MedianFinder medianFinder new MedianFinder(); medianFinder.addNum(1); // arr [1] medianFinder.addNum(2); // arr [1, 2] medianFinder.findMedian(); // 返回 1.5 ((1 2) / 2) medianFinder.addNum(3); // arr[1, 2, 3] medianFinder.findMedian(); // return 2.0提示:-10^5 num 10^5在调用findMedian之前数据结构中至少有一个元素最多5 * 104次调用addNum和findMedian来源295. 数据流的中位数 - 力扣LeetCode解题分析方法堆维护一个最大堆和一个最小堆最大堆存储小于等于中位数的数字最小堆存储大于中位数的数字这样当最大堆大小大于最小堆时最大堆堆顶的元素就是中位数否则就是两个堆顶数字之和除以2。时间复杂度addNum: O(logn) findMedian: O(1)空间复杂度O(n)class MedianFinder { PriorityQueueInteger max; PriorityQueueInteger min; public MedianFinder() { min new PriorityQueue(); max new PriorityQueue(new ComparatorInteger() { public int compare(Integer a, Integer b) { return a b ? -1: 1; } }); min.offer(Integer.MAX_VALUE); max.offer(Integer.MIN_VALUE); } public void addNum(int num) { if (min.peek() num) { min.offer(num); if (max.size() min.size()) { max.offer(min.poll()); } } else { max.offer(num); if (max.size() min.size() 1) { min.offer(max.poll()); } } } public double findMedian() { if (max.size() min.size()) { return max.peek(); } return (max.peek() min.peek()) / 2.0; } } /** * Your MedianFinder object will be instantiated and called as such: * MedianFinder obj new MedianFinder(); * obj.addNum(num); * double param_2 obj.findMedian(); */
