毎日のアルゴリズム: データストリームの中央値

[[431427]]

この記事はWeChatの公開アカウント「3分でフロントエンドを学ぶ」から転載したもので、著者はsisterAnです。この記事を転載する場合は、「3分で学ぶフロントエンド」公式アカウントまでご連絡ください。

中央値は、順序付けられたリスト内の中央の数値です。リストの長さが偶数の場合、中央値は中央の 2 つの数値の平均になります。

例えば、

[2,3,4]の中央値は3

[2,3]の中央値は(2 + 3) / 2 = 2.5である。

次の 2 つの操作をサポートするデータ構造を設計します。

• void addNum(int num) - データ ストリームからデータ構造に整数を追加します。
• double findMedian() – これまでのすべての要素の中央値を返します。

例：

追加番号(1)
追加番号(2)
中央値を見つける() -> 1.5
追加番号(3)
中央値を見つける() -> 2

高度な：

• データ ストリーム内のすべての整数が 0 ～ 100 の範囲内にある場合、アルゴリズムをどのように最適化しますか?
• データ ストリーム内の整数の 99% が 0 ～ 100 の範囲内にある場合、アルゴリズムをどのように最適化しますか?

この動的配列の中央値問題を見ても、興奮しすぎないでください。これはヒープを使用する完璧な例です。ヒープの典型的な応用である中央値問題をテストします。詳細については、「Advanced Front-end Algorithms 9」を参照してください。この記事を読めば、ヒープ ソート、Top K、中央値問題に関する面接を恐れることはなくなります。

解決策: ヒープの使用

解決：

維持するヒープは 2 つあります。

• 最大ヒープ: 最初の n/2 個の小さな要素にアクセスするために使用されます。n が奇数の場合、最初の Math.floor(n/2) + 1 個の要素にアクセスするために使用されます。
• 小さなトップヒープ: 最後のn/2個の小さな要素を保存およびアクセスするために使用されます。

すると、質問によれば、中央値は次のようになります。

• nは奇数です: 中央値は最大ヒープの最上位要素です
• nは偶数です。中央値は、大きなヒープの最上位要素と小さなヒープの最上位要素の平均です。

配列が動的である場合、配列に要素を挿入するたびにヒープをどのように調整しますか?

挿入された要素が最大ヒープの上限より大きい場合、その要素は最小ヒープ内に挿入され、小さい場合は最大ヒープ内に挿入されます。

挿入が完了した後、ビッグトップヒープまたはスモールトップヒープ内の要素数が上記の要件を満たさない場合は、要件が満たされるまで、ビッグトップヒープの最上位要素またはスモールトップヒープの最上位要素を別のヒープへ継続的に移動する必要があります。

コード実装:

 MedianFinder =関数() {
    // 最初の n/2 個の最小要素を格納するための大きなヒープ
    this.lowHeap = 新しい MaxHeap()
    // 小さなトップヒープ。次の n/2 個の最小要素を格納するために使用します。
    this.hightHeap = 新しい MinHeap()
 };
 // 要素を挿入
MedianFinder.prototype.addNum =関数(数値) {
    // 最大ヒープが空の場合、または最大ヒープの先頭の要素がnumより小さい場合は、それを最大ヒープに挿入します
    // それ以外の場合は、小さなトップヒープに挿入します
    if(!this.lowHeap.getSize() || num < this.lowHeap.getHead()) {
        // 最大ヒープの上限より小さい場合は、最大ヒープに挿入します
        this.lowHeap.insert (数値)
    }それ以外{
        // 小さなヒープの先頭より大きい場合は、小さなヒープに挿入します
        this.hightHeap.insert (数値)
    } 
 
    // 最上位ヒープのサイズを比較して、まだバランスが取れているかどうかを確認します
    this.lowHeap.getSize() が this.hightHeap.getSize() より大きい場合、
        // 大きなトップヒープから小さなトップヒープに移行する
        this.hightHeap.insert ( this.lowHeap.removeHead ())
    }
    this.hightHeap.getSize() が this.lowHeap.getSize() より大きい場合、
        // 小さなトップヒープから大きなトップヒープに移行する
        this.lowHeap.insert (this.hightHeap.removeHead())
    }
 };
 // 中央値を取得する
MedianFinder.prototype.findMedian =関数() {
    this.lowHeap.getSize() と this.lowHeap.getSize() が等しい場合、 this.hightHeap.getSize() が返されます。
 (this.lowHeap.getHead() + this.hightHeap.getHead())/2を返します。
    }
 this.lowHeap.getHead()を返す
};

小さなトップヒープの定義は次のとおりです。

 // 小さなトップヒープ
MinHeap =関数() {
    ヒープ = [,] とする
    // ヒープ内の要素数
    this.getSize = () => ヒープの長さ - 1
    // 入れる
    this.insert = (キー) => {
        heap.push(キー)
        // 保存場所を取得する
        i = ヒープの長さ - 1 とします。
        (Math.floor(i/2) > 0 && heap[i] < heap[Math.floor(i/2)]) の場合 {
            swap(heap, i, Math.floor(i/2)); // スワップ
            i = Math.floor(i/2);
        }
    }
    // ヒープヘッダーを削除して戻ります
    this.removeHead = () => {
        ヒープの長さが1より大きい場合
            (heap.length === 2)の場合、heap.pop()を返します。
            num = ヒープ[1]とする
            ヒープ[1] = ヒープ.pop()
            ヒープ化(1)
数値を返す
        }
戻る ヌル 
    }
    // 山の先頭を取得する
    this.getHead = () => {
 heap.length > 1を返すか、heap[1]: null  
    }
    // ヒープ
    ヒープ化 = (i) => {
        k = ヒープの長さ - 1 とします。
        // トップダウンスタッキング
        while( true ) {
            minIndex = i とします
            2*i <= k && ヒープ[2*i] < ヒープ[i]) {
                最小インデックス = 2*i
            }
            2*i+1 <= k && ヒープ[2*i+1] < ヒープ[最小インデックス]) {
                最小インデックス = 2*i+1
            }
            最小インデックスが i の場合
                swap(ヒープ, i, minIndex)
                i = 最小インデックス
            }それ以外{
                壊す
            }
        }
    }
    swap = (arr, i, j) => {とします。
        temp = arr[i]とします。
        arr[i] = arr[j]
        arr[j] =一時 
    }
 }

最大ヒープの定義は次のとおりです。

 // ビッグトップヒープ
MaxHeap =関数() {
    ヒープ = [,] とする
    // ヒープ内の要素数
    this.getSize = ()=>ヒープの長さ - 1
    //最大ヒープに挿入
    this.insert = (キー) => {
        heap.push(キー)
        // 保存場所を取得する
        i = ヒープの長さ - 1 とします。
        (Math.floor(i/2) > 0 && heap[i] > heap[Math.floor(i/2)]) の場合 {
            swap(heap, i, Math.floor(i/2)); // スワップ
            i = Math.floor(i/2);
        }
    }
    // 山の先頭を取得する
    this.getHead = () => {
 heap.length > 1を返すか、heap[1]: null  
    }
    // ヒープヘッダーを削除して戻ります
    this.removeHead = () => {
        ヒープの長さが1より大きい場合
            (heap.length === 2)の場合、heap.pop()を返します。
            num = ヒープ[1]とする
            ヒープ[1] = ヒープ.pop()
            ヒープ化(1)
数値を返す
        }
戻る ヌル 
    }
    // ヒープ
    ヒープ化 = (i) => {
        k = ヒープの長さ - 1 とします。
        // トップダウンスタッキング
        while( true ) {
            maxIndex = iとする
            2*i <= k && ヒープ[2*i] > ヒープ[i]) {
                最大インデックス = 2*i
            }
            2*i+1 <= k && ヒープ[2*i+1] > ヒープ[maxIndex]) {
                最大インデックス = 2*i+1
            }
            if(maxIndex !== i) {
                swap(ヒープ, i, 最大インデックス)
                i = 最大インデックス
            }それ以外{
                壊す
            }
        }
    }
    swap = (arr, i, j) => {とします。
        temp = arr[i]とします。
        arr[i] = arr[j]
        arr[j] =一時 
    }
 }

複雑性分析:

時間計算量: ヒープに要素を挿入する時間計算量は O(logn) で、これはツリーの高さです。ヒープの最上位要素を移動するにはヒープ化も必要なので、時間計算量も O(logn) です。したがって、挿入 ( addNum ) の時間計算量は O(logn) であり、各挿入後に中央値を見つけるにはヒープの最上位要素を返すだけでよく、 findMedian の時間計算量は O(1) です。

空間計算量: O(n)

データストリーム内のすべての整数が0から100の範囲にある場合、カウントソートを使用することができますが、カウントソートの時間計算量はO（n + m）であり、ここでmはデータ範囲を表し、計算量が高いため、ここでは適していません。カウントソートは、静的配列の上位k値に適しています。Leetcode347：上位K高頻度要素

リートコード: https://leetcode-cn.com/problems/find-median-from-data-stream/solution/javascriptshu-ju-liu-de-zhong-wei-shu-by-user7746o/