題目描述
如何得到一個數(shù)據(jù)流中的中位數(shù)？如果從數(shù)據(jù)流中讀出奇數(shù)個數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后位于中間的數(shù)值。如果從數(shù)據(jù)流中讀出偶數(shù)個數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后中間兩個數(shù)的平均值。我們使用Insert()方法讀取數(shù)據(jù)流，使用GetMedian()方法獲取當前讀取數(shù)據(jù)的中位數(shù)。

站在用戶的角度思考問題，與客戶深入溝通，找到宜興網站設計與宜興網站推廣的解決方案，憑借多年的經驗，讓設計與互聯(lián)網技術結合，創(chuàng)造個性化、用戶體驗好的作品，建站類型包括：成都網站制作、成都網站建設、企業(yè)官網、英文網站、手機端網站、網站推廣、主機域名、虛擬空間、企業(yè)郵箱。業(yè)務覆蓋宜興地區(qū)。

# -*- coding: utf-8 -*-
# @Time         : 2019-07-09 10:29
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : getMedianFromStream.py
# @Blog         : https://blog.51cto.com/jayce1111
# @Github       : https://github.com/SysuJayce

class Solution:
    """
    要求一個數(shù)據(jù)流中的中位數(shù)，由于要求的中位數(shù)隨著數(shù)據(jù)流的改變也會發(fā)生變化，因此最樸素的解法就是在
    輸入數(shù)據(jù)的時候直接用一個數(shù)組保存起來，然后在需要返回中位數(shù)的時候先對數(shù)組進行排序然后計算中位數(shù)。

    但是如果要求中位數(shù)，我們其實并不需要得到一個完全有序的數(shù)組。如果數(shù)組的元素個數(shù)是奇數(shù)，那么中位
    數(shù)就是排序后的中間元素，如果是偶數(shù)個，中位數(shù)就是排序后中間兩個元素的平均值?；谶@個觀察，如果
    我們能夠維護兩個指針p1, p2，分別指向當前數(shù)組的左右兩部分，其中p1指向的是左邊部分的最大值，p2
    指向的是右邊部分的最小值。如果當前數(shù)組個數(shù)是奇數(shù)個，那么p1和p2指向同一個位置。

    要實現(xiàn)上述的兩個指針，我們可以利用堆排序中的知識。
    p1相當于指向最大堆的堆頂，p2相當于指向最小堆的堆頂。
    """
    def __init__(self):
        self.min_heap = []
        self.max_heap = []

    def adjustHeap(self, data, idx):
        """
        對于一個堆，當我們對其進行調整的時候，首先要找到給定節(jié)點的子節(jié)點，然后判斷子節(jié)點是否符合
        最大堆/最小堆的要求，如果不符合那就調整。
        :param data: 待調整的堆
        :param idx: 待調整的節(jié)點下標
        """
        length = len(data)  # 當前堆的大小
        temp = data[idx]  # 先記錄待調整節(jié)點的值，最后再放到適當?shù)奈恢弥?        k = 2 * idx + 1  # 左子節(jié)點的下標
        while k < length:  # 我們的調整需要在樹內調整，因此需要限定下標
            # 這里由于我們有兩個堆，而最大堆和最小堆的條件不一樣，所以設置這個分支
            if id(data) == id(self.max_heap):
                # 在最大堆的調整中，我們只需要找到左右子節(jié)點中最大的值然后跟根節(jié)點進行調整
                if k + 1 < length and data[k + 1] > data[k]:
                    k += 1
                # 這里用賦值而非交換，因為待調整節(jié)點可能最終并不位于這個位置，而我們之前已經記錄
                # 好了待調整節(jié)點的值，因此可以放心賦值
                if data[k] > temp:
                    data[idx] = data[k]
                    idx = k  # 賦值完之后需要記錄最新的待調整節(jié)點可能位于的位置
                # 一旦出現(xiàn)子樹符合堆的定義就可以終止調整，因為我們是從下往上構造堆的，只要當前
                # 子樹符合定義，那么再往下的子樹也符合定義
                else:
                    break
            elif id(data) == id(self.min_heap):
                if k + 1 < length and data[k + 1] < data[k]:
                    k += 1
                if data[k] < temp:
                    data[idx] = data[k]
                    idx = k
                else:
                    break
            # 調整完當前子樹之后再調整孫子節(jié)點
            k = 2 * k + 1
        # 最后要記得將待調整節(jié)點的值放到正確的位置
        data[idx] = temp

    def Insert(self, num):
        # 如果已經有偶數(shù)個元素，那么這第奇數(shù)個插入到最小堆(右邊)
        if (len(self.min_heap) + len(self.max_heap)) & 1 == 0:
            # 在插入最小堆之前，需確認待插入元素比最大堆的所有元素都大(即比最大堆的堆頂元素大)
            # 否則需要先插入最大堆，然后將調整后的最大堆的堆頂挪到最小堆中
            if self.max_heap and num < self.max_heap[0]:
                self.max_heap.append(num)
                num = self.max_heap.pop(0)
                self.adjustHeap(self.max_heap, 0)

            # 插入到最小堆后要調整得到新的堆頂。
            # 由于我們是從0開始構造堆的，所以只需要對堆頂進行調整即可
            self.min_heap.append(num)
            self.adjustHeap(self.min_heap, 0)
        # 如果已經有奇數(shù)個元素，那么這第偶數(shù)個元素插入到最大堆(左邊)
        else:
            if self.min_heap and num > self.min_heap[0]:
                self.min_heap.append(num)
                num = self.min_heap.pop(0)
                self.adjustHeap(self.min_heap, 0)

            self.max_heap.append(num)
            self.adjustHeap(self.max_heap, 0)

    def GetMedian(self, num):
        # 這里num參數(shù)是?？途W的OJ有問題，只有這樣才能成功調用GetMedian()
        if not self.min_heap:
            raise Exception("No numbers are available.")

        if (len(self.min_heap) + len(self.max_heap)) & 1 == 0:
            return (self.min_heap[0] + self.max_heap[0]) / 2.0
        else:
            return self.min_heap[0]

def main():
    solution = Solution()
    nums = [5, 2, 3, 4, 1, 6, 7, 0, 8]
    for num in nums:
        solution.Insert(num)
        print(solution.GetMedian(num))

if __name__ == '__main__':
    main()

網站標題：劍指offer：數(shù)據(jù)流中的中位數(shù)
文章出自：http://chinadenli.net/article2/giejic.html

成都網站建設公司_創(chuàng)新互聯(lián)，為您提供軟件開發(fā)、微信公眾號、用戶體驗、服務器托管、網站設計公司、小程序開發(fā)

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)