Leetcode:295. 数据流的中位数

题目描述

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

[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 范围内，你将如何优化你的算法？

思路

思路1：借用插入排序方法，每次插入后保持有序

使用插入排序思路，每次插入新的数据后数据保持有序，这样时间复杂度主要来自于插入的O(n)
// TODO:其他思路

代码

代码1：插入排序思路

class MedianFinder {
    private List list;

    /** initialize your data structure here. */
    public MedianFinder() {
        list = new ArrayList<>();
    }
    
    public void addNum(int num) {
        if (list.isEmpty()){
            list.add(num);
            return;
        }
        int insertIndex = 0;
        for(; insertIndex < list.size(); insertIndex++){
            if(list.get(insertIndex) > num){
                break;
            }
        }
        list.add(insertIndex, num);
    }
    
    public double findMedian() {
        if (list.size() % 2 != 0){
            return list.get(list.size() / 2);
        } else {
            return 1.0 * (list.get(list.size() / 2 - 1) + list.get(list.size() / 2)) / 2;
        }
    }
}

复杂度分析

代码1时间复杂度

主要是插入排序的时间每次为O(n)

代码1空间复杂度

$O(n)$