2021-11-03：数据流的中位数。中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。例如，[2,3

福大大架构师每日一题

发布于 2021-11-09 10:59:54

5300

发布于 2021-11-09 10:59:54

2021-11-03：数据流的中位数。中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。例如，[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 范围内，你将如何优化你的算法？力扣295。

答案2021-11-03：

大根堆和小根堆。

addNum方法时间复杂度：O(logN)。

findMedian方法时间复杂度：O(logN)。

代码用golang编写。代码如下：

package main

import (
    "fmt"
    "sort"
)

func main() {
    finder := NewMedianFinder()
    finder.addNum(1)
    finder.addNum(2)
    fmt.Println(finder.findMedian())
    finder.addNum(3)
    fmt.Println(finder.findMedian())
}

type MedianFinder struct {
    maxh []int
    minh []int
}

func NewMedianFinder() *MedianFinder {
    res := &MedianFinder{}
    res.maxh = make([]int, 0)
    res.minh = make([]int, 0)
    return res
}

func (this *MedianFinder) addNum(num int) {
    sort.Ints(this.maxh)
    sort.Reverse(sort.IntSlice(this.maxh))
    sort.Ints(this.minh)
    if len(this.maxh) == 0 || this.maxh[0] >= num {
        this.maxh = append(this.maxh, num)
    } else {
        this.minh = append(this.minh, num)
    }
    this.balance()
}

func (this *MedianFinder) findMedian() float64 {
    sort.Ints(this.maxh)
    sort.Reverse(sort.IntSlice(this.maxh))
    sort.Ints(this.minh)
    if len(this.maxh) == len(this.minh) {
        return float64(this.maxh[0]+this.minh[0]) / float64(2)
    } else {
        if len(this.maxh) > len(this.minh) {
            return float64(this.maxh[0])
        } else {
            return float64(this.minh[0])
        }
    }
}

func (this *MedianFinder) balance() {
    sort.Ints(this.maxh)
    sort.Reverse(sort.IntSlice(this.maxh))
    sort.Ints(this.minh)
    if Abs(len(this.maxh)-len(this.minh)) == 2 {
        if len(this.maxh) > len(this.minh) {
            this.minh = append(this.minh, this.maxh[0])
        } else {
            this.maxh = append(this.maxh, this.minh[0])
        }
    }
}

func Abs(a int) int {
    if a < 0 {
        return -a
    } else {
        return a
    }
}

执行结果如下：