首页 > 试题广场 >

数据流中的中位数

[编程题]数据流中的中位数

热度指数：428759 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

数据范围：数据流中数个数满足 $1 \le n \le 1000 \$ ，大小满足 $1 \le val \le 1000 \$

进阶：空间复杂度 $O(n) \$ ，时间复杂度 $O(nlogn) \$

示例1

输入

[5,2,3,4,1,6,7,0,8]

输出

"5.00 3.50 3.00 3.50 3.00 3.50 4.00 3.50 4.00 "

说明

数据流里面不断吐出的是5,2,3...,则得到的平均数分别为5,(5+2)/2,3...

示例2

输入

[1,1,1]

输出

"1.00 1.00 1.00 "

算法知识视频讲解

Python 3

蓝鲸与风

# -*- coding:utf-8 -*-
import heapq
class Solution:
    def __init__(self):
        self.maxq=[]
        self.minq=[]
    #import heapq
    def Insert(self, num):
        # write code here
        heapq.heappush(self.minq,num)#先插入小顶堆
        #平衡堆,注意需要加入相反数
        #！！！！！注意大顶堆的构建
        heapq.heappush(self.maxq,-heapq.heappop(self.minq))
        if len(self.minq) < len(self.maxq):
            #大顶堆的顶加入小顶堆
            heapq.heappush(self.minq, -heapq.heappop(self.maxq))
    #小顶堆为中位数的右边，大顶堆为中位数的左边
    def GetMedian(self):
        # write code here
        if len(self.minq) < len(self.maxq):
            return -self.maxq[0]
        elif len(self.minq) > len(self.maxq):
            return self.minq[0]
        else:
            return (self.minq[0]-self.maxq[0] )/2

发表于 2022-08-20 13:01:00 回复(0)

Python 3

YiMo_以沫

1. 二分，每次插入值的时候用二分找出要插入的位置的下标，始终保持数据一直在有序的状态。

时间复杂度：二分O(logN)，插入数组O(N)，所以为O(N).

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.arr = []
        self.length = 0
    
    def Insert(self, num):
        # write code here
        if not self.length: self.arr.append(num)
        else:
            index = self.binarySearch(num)
            self.arr.insert(index, num)
        self.length += 1
        
    def GetMedian(self):
        # write code here
        if not self.length: return 0
        if self.length & 1:
            return self.arr[self.length >> 1]
        else:
            return (self.arr[self.length >> 1] + self.arr[(self.length >> 1) - 1]) / 2
    
    def binarySearch(self, num):
        left, right = 0, self.length - 1
        while left <= right:
            mid = (right + left) >> 1
            if self.arr[mid] >= num: right = mid - 1
            else: left = mid + 1
        return left

发表于 2022-06-21 16:22:30 回复(0)

Python 3

东方佑

# -*- coding:utf-8 -*-
class Solution:
    def  __init__(self):
        self.data=[]
    def Insert(self, num):
        # write code here
        self.data.append(num)

    def GetMedian(self):
        # write code here
        x=sorted(self.data)
        x_index=len(x)//2
        if x_index==0 and len(x)==1:
            return x[0]/1.0



        if len(x)%2==0:
#             print(x_index,x)
#             midea=0
            midea=(x[x_index-1]+x[x_index])/2
        else:
            midea=x[x_index]
#             midea=0


        return midea

发表于 2022-06-08 17:53:18 回复(0)

Python 3

Vivimore

前后段使用的都是小根堆，只是前半段的小根堆加入的是取负号的元素值，从前半段小根堆pop出最小值（负值），取上负号就是最大值了

from heapq import *  # 导入小根堆
class Solution:
    pre = []  # 前半部分
    after = []  # 后半部分
    def Insert(self, num):
        pre = self.pre
        after = self.after
        # 往后半部分添加元素
        # 每次从后半部分pop出一个最小值加入前半部分
        # 相当于后半部分长度不变，前半部分长度+1
        heappush(pre, -heappushpop(after, num))
        # 维持前后段元素个数相差不超过1
        if len(after) < len(pre):
            # 从前半部分pop出一个最小值（这个值是负数，添负号后就是最大值）
            # 将添负号后的值（前半部分最大值）加入到后半部分
            heappush(after, -heappop(pre)) 
    def GetMedian(self):
        pre = self.pre
        after = self.after
        # 后半部分比前半部分多一位，中位数 = 后半部分[0]
        if len(after) > len(pre):
            return after[0]
        else:
            # 中位数 = （后半部分最小值 + 前半部分最大值 ）/ 2 
            # 因为前部分小根堆里的元素是负值
            # pop出最小的负值取负号就能拿到前半部分的最大值
            return (after[0] - pre[0]) / 2

发表于 2022-05-18 17:06:05 回复(0)

Python 3

香蕉泥Ge布呐呐呀

# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.data = []
self.nums = 0
def DataSort(self, datalist, num):
if len(datalist) == 0:
return 0
else:
l, r = 0, len(datalist)-1
while l <= r:
mid = (l+r)//2
if datalist[mid] > num:
r = mid - 1
elif datalist[mid] < num:
l = mid + 1
elif datalist[mid] == num:
return mid
return l
def Insert(self, num):
# write code here
index = self.DataSort(self.data, num)
self.data = self.data[:index] + [num] + self.data[index:]
self.nums += 1
def GetMedian(self):
# write code here
mid = self.nums//2
if self.nums%2==0:
return (self.data[mid]+self.data[mid-1])/2
else:

return self.data[mid]

二分满足时间复杂度 O(nlogn)

发表于 2022-04-10 12:37:16 回复(0)

Python 3

小小小小燃

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stream = []
        
    def Insert(self, num):
        
        # 处理边界情况
        if len(self.stream) == 0:
            self.stream.append(num)
            return
        
        left = 0
        right = len(self.stream)
        while left < right:
            mid = int(0.5 * (left + right))
            if self.stream[mid] <= num:
                left = mid + 1
            else:
                right = mid
        
        self.stream = self.stream[:left] + [num] + self.stream[left:]        
        
    def GetMedian(self):
        # write code here
#         self.stream = self.quick_sort(self.stream)
        lens = len(self.stream)
        
        # 处理边界情况
        if len(self.stream) == 1:
            return self.stream[0]
        
        tmp = int(lens / 2)
        if lens % 2 == 0:
            return 0.5 * (self.stream[tmp] + self.stream[tmp - 1])
        else:
            return self.stream[tmp]

发表于 2022-04-09 22:07:15 回复(0)

Python 3

Virtual~

二分查找找到插入的位置：

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.array = []
        
    def Insert(self, num):
        # write code here
        n = len(self.array)
        if n == 0:
            self.array.append(num)
        else:
            pos = -1
            left, right = 0, n-1
            while left <= right:
                pos = (left + right) // 2
                if self.array[pos] < num:    left += 1
                elif self.array[pos] > num:    right -= 1
                else:
                    break
            if pos == right:
                pos += 1
            self.array.insert(pos, num)
        print("array: ", self.array)
        
    def GetMedian(self):
        # write code here
        mid_idx = len(self.array) // 2
        if len(self.array) % 2 == 1:
            return self.array[mid_idx]
        else:
            return (self.array[mid_idx] + self.array[mid_idx-1]) / 2

发表于 2022-03-03 10:46:39 回复(0)

Python 3

牛客38477449号

# -*- coding:utf-8 -*-
import heapq
class Solution:
    def __init__(self):
        self.big = []
        self.small = []
        heapq.heapify(self.big)
        heapq.heapify(self.small)
    def Insert(self, num):
        # write code here
        if len(self.big) == 0:
            heapq.heappush(self.big, -num)
        else:
            if num <= -self.big[0]:
                heapq.heappush(self.big, -num)
            else:
                heapq.heappush(self.small, num)
        if len(self.big) - len(self.small) >= 2:
            heapq.heappush(self.small, -heapq.heappop(self.big))
        if len(self.small) - len(self.big) >= 2:
            heapq.heappush(self.big, -heapq.heappop(self.small))
    def GetMedian(self):
        # write code here
        if len(self.big) > len(self.small):
            return -self.big[0]
        elif len(self.small) > len(self.big):
            return self.small[0]
        else:
            return (-self.big[0] + self.small[0]) / 2

发表于 2021-09-03 18:12:23 回复(0)

Python 3

tantantansq

import heapq
class Solution:
    def __init__(self):
        self.heapmin=[]  #小顶堆
        self.heapmax=[]  #大顶堆
        
        
    def Insert(self, num):
        # write code here
        if len(self.heapmin)==len(self.heapmax):  #优先插入到小顶堆中
            if len(self.heapmax)==0&nbs***bsp;-heapq.nsmallest(1, self.heapmax)[0]<=num:
                heapq.heappush(self.heapmin,num)
            else:
                temp=-self.heapmax.pop(0)
                heapq.heappush(self.heapmin, temp)
                heapq.heappush(self.heapmax, -num)
        else:
            if heapq.nsmallest(1, self.heapmin)[0]>=num:
                heapq.heappush(self.heapmax,-num)
            else:
                temp=self.heapmin.pop(0)
                heapq.heappush(self.heapmax, -temp)
                heapq.heappush(self.heapmin, num)
        
        
    def GetMedian(self):
        # write code here
        if len(self.heapmin)==len(self.heapmax):
            return (heapq.nsmallest(1, self.heapmin)[0]-heapq.nsmallest(1, self.heapmax)[0])/2
        return heapq.nsmallest(1, self.heapmin)[0]

发表于 2021-08-09 01:06:01 回复(0)