10

私は配列を持っているので、2a = { 1,4,5,6,2,23,4,2}; から 6 までの配列位置の中央値 (奇数合計項) を見つける必要があるとしましょう。a[1]a[5]arr[0]arr[4]arr[2]

しかし、ここでは、ある配列から別の配列に値を入れるたびに、最初の配列の値が同じままになるようにします。第二に、私はソートしたので、この手順はかなり時間がかかります**time**. だから私はこれを別の方法で行うことができる方法があるかどうか知りたいreduce my computation time.

ウェブサイト、理解すべき資料、何を、どのように行うべきか?

4

6 に答える 6

22

O(N)std::nth_elementからの使用:<algorithm>

nth_element(a, a + size / 2, a + size);
median = a[size/2];
于 2012-06-16T16:56:22.390 に答える
15

O(n) 時間でソートせずに中央値を見つけることができます。これを行うアルゴリズムは、選択アルゴリズムと呼ばれます。

于 2012-06-16T16:15:31.543 に答える
6

同じアレイに対して複数のクエリを実行している場合は、セグメント ツリーを使用できます。これらは通常、範囲の最小/最大および範囲の合計クエリを実行するために使用されますが、範囲の中央値を実行するように変更できます。

n 間隔のセットのセグメント ツリーは、O(n log n) ストレージを使用し、O(n log n) 時間で構築できます。範囲クエリは O(log n) で実行できます。

範囲セグメント ツリーの中央値の例:

セグメント ツリーを下から上に構築します (上から下に更新します)。

                    [5]
        [3]                     [7]
 [1,2]        [4]         [6]         [8] 
1     2     3     4     5     6     7     8

ノードがカバーするインデックス:

                    [4]
        [2]                     [6]
 [0,1]        [3]         [5]         [7] 
0     1     2     3     4     5     6     7

4 ～ 6 の範囲インデックスの中央値のクエリは、次の値のパスをたどります。

                    [4]
                          [5]
0     1     2     3     4     5     6     7

中央値を検索すると、クエリの合計要素数 (3) がわかり、その範囲の中央値は 2 番目の要素 (インデックス 5) になります。したがって、基本的には、値 [1,2] (インデックス 0,1) を持つノードであるインデックスを含む最初のノードを検索しています。

範囲 3 ～ 6 の中央値の検索は、同じノードにある 2 つのインデックス (4,5) を検索する必要があるため、もう少し複雑です。

                    [4]
                                [6]
                          [5] 
0     1     2     3     4     5     6     7

セグメントツリー

セグメント ツリーの範囲最小クエリ

于 2012-06-16T18:08:37.333 に答える
1

9要素未満の配列の中央値を見つけるには、挿入ソートのようなソートアルゴリズムを使用するのが最も効率的だと思います。複雑さは悪いですが、クイックソートのようなより優れたアルゴリズムの複雑さのために、このような小さな配列のk場合、挿入ソートは非常に効率的です。独自のベンチマークを行ってください。ただし、シェル ソートやクイックソートよりも挿入ソートの方が優れた結果が得られると言えます。

于 2012-06-16T16:21:15.503 に答える
0

最善の方法は、配列の k 番目に大きい要素をカウントする中央値アルゴリズムの中央値を使用することだと思います。ここでアルゴリズムの全体的なアイデアを見つけることができます: Median of Medians in Java、ウィキペディア: http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithmまたは単にインターネットを閲覧します。実装中にいくつかの一般的な改善を行うことができます (特定の配列の中央値を選択するときにソートを回避します)。ただし、要素数が 50 未満の配列の場合は、中央値アルゴリズムの中央値よりも挿入並べ替えを使用する方が効率的であることに注意してください。

于 2012-06-16T18:35:39.427 に答える
0

既存のすべての回答には、特定の状況でいくつかの欠点があります。

  1. 中央値を得るために配列全体をソートする必要はなく、複数の部分範囲の中央値が見つかる場合は追加の配列が必要になるため、部分範囲全体のソートはあまり効率的ではありません。
  2. を使用するstd::nth_element方が効率的ですが、それでもサブ範囲が変更されるため、追加の配列が必要です。
  3. セグメント ツリーを使用すると効率的なソリューションが得られますが、構造を自分で実装するか、サード パーティのライブラリを使用する必要があります。

このため、std::map選択ソートアルゴリズムを使用し、それに触発されたアプローチを投稿しています。

  1. まず、最初のサブレンジ内の要素の頻度を のオブジェクトに収集しますstd::map<int, int>。

  2. このオブジェクトを使用すると、長さが の部分範囲の中央値を効率的に見つけることができますsubrangeLength。

    double median(const std::map<int, int> &histogram, int subrangeLength)
{
    const int middle{subrangeLength / 2};
    int count{0};


    /* We use the fact that keys in std::map are sorted, so by simply iterating
       and adding up the frequencies, we can find the median. */
    if (subrangeLength % 2 == 1) {
        for (const auto &freq : histogram) {
            count += freq.second;
            /* In case where subrangeLength is odd, "middle" is the lower integer bound of
               subrangeLength / 2, so as soon as we cross it, we have found the median. */
            if (count > middle) {
                return freq.first;
            }
        }
    } else {
        std::optional<double> medLeft;
        for (const auto &freq : histogram) {
            count += freq.second;
            /* In case where subrangeLength is even, we need to pay attention to the case when
               elements at positions middle and middle + 1 are different. */
            if (count == middle) {
                medLeft = freq.first;
            } else if (count > middle) {
                if (!medLeft) {
                    medLeft = freq.first;
                }
                return (*medLeft + freq.first) / 2.0;
            }
        }
    }

    return -1;
}

  3. 次の部分範囲の中央値を取得したい場合は、削除する要素の頻度を減らしてヒストグラムを更新し、新しい要素を追加/増やします (std::mapこれは一定時間で行われます)。次に、中央値を再度計算し、すべての部分範囲を処理するまでこれを続けます。

于 2019-10-18T15:29:05.823 に答える