leetcode295-数据流的中位数

原题

中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。

例如,

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构:

  • void addNum(int num) - 从数据流中添加一个整数到数据结构中。
  • double findMedian() - 返回目前所有元素的中位数。

示例:

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2

进阶:

  1. 如果数据流中所有整数都在 0 到 100 范围内,你将如何优化你的算法?
  2. 如果数据流中 99% 的整数都在 0 到 100 范围内,你将如何优化你的算法?

解法

思想

求中位树可以维护两个堆,一个大顶堆用于存放数据较小的半部分,一个小顶堆用于存放数据较大的半部分。

代码

public class MedianFinder {

    private int count;
    private PriorityQueue<Integer> maxheap;
    private PriorityQueue<Integer> minheap;

    /**
     * initialize your data structure here.
     */
    public MedianFinder() {
        count = 0;
        maxheap = new PriorityQueue<>((x, y) -> y - x);
        minheap = new PriorityQueue<>();
    }

    public void addNum(int num) {
        count += 1;
        maxheap.offer(num);
        minheap.add(maxheap.poll());
        if (count%2 != 0) {
            maxheap.add(minheap.poll());
        }
    }

    public double findMedian() {
        if (count%2 != 0) 
            return (double) maxheap.peek();
        else
            return (double) (maxheap.peek() + minheap.peek()) / 2;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode295-%e6%95%b0%e6%8d%ae%e6%b5%81%e7%9a%84%e4%b8%ad%e4%bd%8d%e6%95%b0/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年2月12日
下一篇 2020年2月12日

相关推荐

  • leetcode700-二叉搜索树中的搜索

    原题 给定二叉搜索树(BST)的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL。 例如, 给定二叉搜索树…

    算法 2020年1月16日
    090
  • 剑指offer40-最小的k个数

    原题(来源Leetcode) 输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。 示例 1: …

    算法 2020年3月20日
    0380
  • 使用递归函数逆序一个栈

    原题(来源:牛客网) 一个栈依次压入1,2,3,4,5那么从栈顶到栈底分别为5,4,3,2,1。将这个栈转置后,从栈顶到栈底为1,2,3,4,5,也就是实现了栈中元素的逆序,请设计…

    算法 2020年4月19日
    0250
  • leetcode530-二叉搜索树的最小绝对差

    原题 给定一个所有节点为非负值的二叉搜索树,求树中任意两节点的差的绝对值的最小值。 示例: 输入:    1    &n…

    算法 2020年2月22日
    01320
  • 二叉树中序遍历-折纸问题

    原题(来源牛客网) 请把纸条竖着放在桌⼦上,然后从纸条的下边向上⽅对折,压出折痕后再展开。此时有1条折痕,突起的⽅向指向纸条的背⾯,这条折痕叫做“下”折痕 ;突起的⽅向指向纸条正⾯…

    2020年4月27日
    02490
  • leetcode287-寻找重复数

    原题 给定一个包含 n + 1 个整数的数组 nums ,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。 …

    2020年1月7日
    080
  • leetcode42-接雨水

    原题 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高…

    2020年1月23日
    0290
  • leetcode104-二叉树的最大深度

    原题 给定一个二叉树,找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例:给定二叉树 [3,9,20,null…

    算法 2020年1月11日
    080
  • leetcode454-四数相加II

    原题 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l] = 0。 为…

    算法 2019年12月27日
    070
  • leetcode990-等式方程的可满足性

    原题 给定一个由表示变量之间关系的字符串方程组成的数组,每个字符串方程 equations[i] 的长度为 4,并采用两种不同的形式之一:"a==b" 或 "a!=b"。在这里,a…

    算法 2020年6月8日
    090

发表回复

登录后才能评论