首页 > 试题广场 >

实时中位数

[编程题]实时中位数

热度指数：5421 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个int数组A，初始为空，现生成n个随机数依次传入数组中，将返回一个int数组，数组中的每个元素代表每次传入随机数到数组A后A中全部数的中位数。(若传入了偶数个数字则令中位数为第n/2小的数字，n为已传入数字个数)保证n小于等于1000。

测试样例：

[1,2,3,4,5,6],6

返回：[1,1,2,2,3,3]

算法知识视频讲解

Python

华科平凡

python solution

使用bisect模块，时间复杂度为nlogn

# -*- coding:utf-8 -*-

import bisect
class Middle:
    def getMiddle(self, A, n):
        mid,res,count=[],[],0

        for i in A:
            bisect.insort(mid,i)
            count+=1
            if count%2==0:
                res.append((mid[count//2-1]))
            else:
                res.append(mid[count//2])
        return res

编辑于 2017-10-31 16:41:28 回复(0)