0

重複の可能性:
配列内の反転のカウント

ソートされていない配列が与えられた場合、arr可能なすべてのインデックスのペアをどのように数えます(i, j)かarr[i] < arr[j]? 複雑さは線形または線形に近い必要があります (O(n^2)解決策は明らかです)。

編集：

すみません、言い忘れましたi < jがインデックスの状態です。

4

3 に答える 3

2

ヒント：

インデックス（i、j）の各ペアについて、これらのステートメントの1つだけが真です。

(a[i]<a[j])、、。(a[i]=a[j])_(a[i]>a[j])

配列を調べて、a[]の各値のインスタンスの数を数える必要があります

次に、それは組み合わせ論の問題です...

于 2012-12-09T20:19:18.517 に答える
1

[重要]: 以下は、i < j という条件がない最初の質問に対する回答です。

で並べ替えてO(N * log(N))、 で答えを見つけることができO(N)ますO(N * log(N))。合計で表示されます。以下は、2番目の部分のコードです（配列がソートされた後）：

int count = 0;
int curBefore = 0;
for (int i = 1; i < sorted.Length; i++)
{
    if (sorted[i] > sorted[i - 1])
    {
        curBefore = i;
    }
    count += curBefore;
}

そして、はい、線形 (辞書操作は一般的に線形ではないため、疑似) ソリューションもあります! ただし、追加のメモリと辞書のようなデータ構造の使用が必要です。

int res = sorted.Length * (sorted.Length - 1) / 2;
Dictionary<int, int> dict = new Dictionary<int, int>();
for (int i = 0; i < sorted.Length; i++)
{
    if (!dict.ContainsKey(sorted[i]))
    {
        dict.Add(sorted[i], 0);
    }
    dict[sorted[i]]++;
}
foreach (var pair in dict)
{
    res -= (pair.Value - 1) * pair.Value / 2;
}
于 2012-12-09T20:25:20.333 に答える
0

カスタマイズされた二分木を使用して、このカウントをオンザフライで計算できます。したがって、各ノードには次の 3 つの値が含ま(v, lc, ec)れます。ご覧のとおり、これらのカウンターは、ツリーに新しい値を挿入すると更新されます。vlcecv

最終的な答えはグローバル変数に保持され、新しい値がツリーに挿入されるたびに更新されます。アイデアは、新しい値がツリーに挿入されると、特定のパスを通過し、このパスに沿ったノードは、通過する値よりも小さい値がいくつ存在するかを正確に認識するため、これらのノードで最終的な答え適宜更新できます。

最終的な回答は、新しい値が現在のノードの値より大きい場合 (つまり、新しい値を右のサブツリーに転送する場合) にのみ更新されることに注意してください。これは、追加の制約があるためですi < j。

お役に立てれば！

于 2012-12-09T21:41:14.177 に答える