LEETCODE 295. Find Median from Data Stream 解题思路分析

题目大意:

数据流的中位数

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

例如,

[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

进阶:

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=295

解题思路分析:

本题虽然是Hard级别,但是难度并不大,这里分享两种解法。

解法一:二分查找

我们先建立一个List集合,用于存放所有输入的数字,通过addNum方法向list中插入数字时,使用二分查找的方式找到插入下标,以保证数组中的所有数字按照升序排列。findMedian方法中,判断当前list的数据个数,当为奇数时直接返回下标为list.size()/2的中位数,为偶数时返回下标为 list.size()/2 以及 list.size()/2 -1 数字和的一半即可。

实现代码:

// 记录所有输入过的数字
List<Integer> list = new ArrayList<>();
public MedianFinder() {

}

public void addNum(int num) {
    // 二分查找当前数字应插入的位置,保证list内元素升序排列
    int left=0,right=list.size()-1;
    while(left<=right){
        int mid = (left+right)/2;
        if(list.get(mid)==num){
            left=mid;
            break;
        }else if(list.get(mid)<num){
            left=mid+1;
        }else{
            right=mid-1;
        }
    }
    list.add(left,num);
}

public double findMedian() {
    // 找到list的中间数返回
    if(list.size()==0) return 0;
    int mid=list.size()/2;
    if(list.size()%2==0){
        return (list.get(mid)+list.get(mid-1))/2.0;
    }else{
        return list.get(mid);
    }
}

本解法执行时间为79ms。

Runtime: 79 ms, faster than 32.78% of Java online submissions for Find Median from Data Stream.

Memory Usage: 67 MB, less than 52.54% of Java online submissions for Find Median from Data Stream.


解法二:PriorityQueue (heap)

本解法要使用到两个PriorityQueue。原则上只要我们能将所有数字分成2组,2组的元素个数最多相差为1,并且保证其中一组元素中的数字都大于等于另外一组元素,那么我们很容易在两组数中找到符合条件的中位数。

解题时,建立两个 PriorityQueue 定义为smallHalf和largeHalf,分别代表较小的一半数字与较大的另一半数字。其中smallHalf设定为降序排列,largeHalf为升序排列,插入数据时,当 smallHalf 与 largeHalf 的元素个数相同时,我们向 smallHalf 插入当前数字,插入后,由于要保证 smallHalf 中的元素都小于等于 largeHalf 中的元素,所以我们需要将 smallHalf 中最大的一个元素移动到 largeHalf 中。

当 smallHalf 与 largeHalf 的元素个数不同时,我们向 largeHalf 插入当前元素,同时还需要将 largeHalf 中最小的元素移动到 smallHalf 中。

findMedian方法中,判断 smallHalf 与 largeHalf 的元素个数是否相同,相同时,从 smallHalf 取一个最大值,并从 largeHalf 取一个最小值,求平均数返回即可。如果 smallHalf 的元素个数大于 largeHalf,直接返回 smallHalf 中最大元素,反之返回 largeHalf 中最小元素。

实现代码:

    PriorityQueue<Integer> smallHalf = new PriorityQueue<>((a,b)->b-a);
    PriorityQueue<Integer> largeHalf = new PriorityQueue<>();
    /** initialize your data structure here. */
    public MedianFinder() {
        
    }
    
    public void addNum(int num) {
        if(smallHalf.size()==largeHalf.size()){
            smallHalf.offer(num);
            largeHalf.offer(smallHalf.poll());
        }else{
            largeHalf.offer(num);
            smallHalf.offer(largeHalf.poll());
        }
    }
    
    public double findMedian() {
        if(smallHalf.size()==largeHalf.size()){
            return (smallHalf.peek()+largeHalf.peek())/2.0;
        }else if(smallHalf.size()>largeHalf.size()){
            return smallHalf.peek();
        }else{
            return largeHalf.peek();
        }
    }

本解法执行时间为72ms。

Runtime: 72 ms, faster than 61.58% of Java online submissions for Find Median from Data Stream.

Memory Usage: 58.6 MB, less than 98.31% of Java online submissions for Find Median from Data Stream.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-295-find-median-from-data-stream-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。