1

誰かがc++のダイナミックレンジの高速中央値検出の実装への方法やリンクを提案できますか？たとえば、プログラムの反復で範囲が拡大し、実行ごとに中央値を見つけたいとします。

Range
4
3,4
8,3,4
2,8,3,4
7,2,8,3,4

したがって、上記のコードは、最終的に各行に5つの中央値を生成します。

4

3 に答える 3

4

配列のソートされたコピーを追跡せずに取得できる最善の方法は、古い中央値を再利用し、次に大きい値の線形時間検索でこれを更新することです。これは単純に聞こえるかもしれませんが、解決しなければならない問題があります。

次のリストを検討してください（理解しやすいように並べ替えられていますが、任意の順序で保持しています）。

    1, 2, 3, 3, 3, 4, 5
//           *

したがって、ここでは、中央値は3（リストがソートされているため、中央の要素）です。ここで、中央値よりも大きい数値を追加すると、中央値がインデックスの半分だけ右に「移動」する可能性があります。2つの問題があります。どうすれば半分のインデックスで進めることができますか？（定義によれば、中央値は次の2つの値の平均値です。）そして3、中央値しかわからないのに、どのようにして中央値がどこにあるかを知ることができ3ますか？

これは、現在の中央値だけでなく、同じ値の数値内の中央値の位置も格納することで解決できます。ここでは、2番目であるため、 「インデックスオフセット」があります。リストに以上の数値を追加すると、インデックスオフセットがに変更されます。3未満の数値を追加すると、に変更されます。1331.50.5

この数がゼロ未満になると、中央値が変化します。また、等しい数の数（マイナス）を超える場合も変更する必要があります1。この場合2、新しい中央値が最後の等しい数よりも大きいことを意味します。どちらの場合も、次に小さい/次に大きい数を検索し、中央値を更新する必要があります。インデックスオフセットの上限（この場合2）を常に知るには、等しい数のカウントも追跡する必要があります。

これにより、線形時間で中央値の更新を実装する方法の大まかなアイデアが得られるはずです。

于 2013-03-26T17:04:01.813 に答える
0

min-max-medianヒープを使用できると思います。配列が更新されるたびに、新しい中央値を見つけるために必要なのはlog（n）時間だけです。min-max-medianヒープの場合、ルートは中央値、左側のツリーはmin-maxヒープ、右側はmax-minヒープです。詳細については、「最小-最大ヒープと一般化された優先度キュー」を参照してください。

于 2019-12-19T09:31:38.983 に答える
-1

以下のいくつかのコードをフィンします、私はあなたの必要な出力を与えるためにこのスタックを作り直しました

    private void button1_Click(object sender, EventArgs e)
    {
        string range = "7,2,8,3,4";
        decimal median = FindMedian(range);
        MessageBox.Show(median.ToString());

    }

    public decimal FindMedian(string source)
    {
        // Create a copy of the input, and sort the copy

        int[] temp = source.Split(',').Select(m=> Convert.ToInt32(m)).ToArray();
        Array.Sort(temp);

        int count = temp.Length;
        if (count == 0) {
            throw new InvalidOperationException("Empty collection");
        }
        else if (count % 2 == 0) {
            // count is even, average two middle elements
            int a = temp[count / 2 - 1];
            int b = temp[count / 2];
            return (a + b) / 2m;
        }
        else {
            // count is odd, return the middle element
            return temp[count / 2];
        }
    }
于 2013-03-26T17:16:40.670 に答える