3

バイナリ インデックス ツリー (BIT) で特定の累積頻度のインデックスを見つけようとしていました。

この問題を O(log(n)*log(n)) で解決するには、バイナリ検索と任意のインデックスで累積頻度を計算する関数を使用して実装することで解決できました。

しかし、私はこの問題を O(log(n)) で解決することを考えていました。

だから助けてください。

4

1 に答える 1

0

トップコーダー チュートリアルのこのアルゴリズムは、O(logn) で指定された累積頻度で最大のインデックスを見つける方法を示しています。

与えられたキュマルチブ頻度を持つインデックスを見つけるための素朴で最も単純な解決策は、すべてのインデックスを単純に繰り返し、累積頻度を計算し、それが与えられた値に等しいかどうかをチェックすることです。負の周波数の場合、これが唯一の解決策です。ただし、ツリーに非負の頻度しかない場合 (つまり、より大きなインデックスの累積頻度が小さくないことを意味します)、二分探索の修正である対数アルゴリズムを理解できます。すべてのビット (最上位のものから開始) を調べ、インデックスを作成し、現在のインデックスと指定された値の累積頻度を比較し、結果に従って、間隔の下半分または上半分を取得します (二分探索と同様) ）。

// if in tree exists more than one index with a same
// cumulative frequency, this procedure will return 
// the greatest one
int findG(int cumFre){
    int idx = 0;

    while ((bitMask != 0) && (idx < MaxVal)){
        int tIdx = idx + bitMask;
        if (cumFre >= tree[tIdx]){ 
            // if current cumulative frequency is equal to cumFre, 
            // we are still looking for higher index (if exists)
            idx = tIdx;
            cumFre -= tree[tIdx];
        }
        bitMask >>= 1;
    }
    if (cumFre != 0)
        return -1;
    else
        return idx;
}
于 2013-05-28T17:53:11.137 に答える