剑指offer 面试41题

面试41题：

题目：数据流中的中位数

题：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

解题思路一：直接法，排序后求中位数

解题代码：

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

class Solution:

    def __init__(self):

        self.array=[]

    def Insert(self, num):

        # write code here

        self.array.append(num)

        self.array.sort()

    def GetMedian(self,M):

        # write code here

        length=len(self.array)

        if len(self.array)%2==1:

            return self.array[length//2]

        else:

            return (self.array[length//2-1]+self.array[length//2])/2.0

解题思路二：使用最大堆、最小堆。

解题代码：略。（待补充）

巴特西

剑指offer 面试41题

最新文章

热门文章