1

私はプログラミングのインタビューでこの問題に遭遇しましたが、今ではまったくわかりません。

長さが n のリストで、その中の要素はすべて順不同の正の整数です。すべての可能なトリプル (a、b、c) を見つけるには、a < b < c であり、リスト内で a が b の前に、b が c の前に表示されます。

そして、アルゴリズムの時間の複雑さを分析します。

4

3 に答える 3

4

O(n^3) よりも高速な一般的なアルゴリズムはありません。ソートされた個別の要素の入力が与えられた場合、出力のサイズは O(n^3) になるため、出力を生成するには時間が比例します。実際、ランダムに生成された整数のリストでさえ、定数因数まではすでに n^3 のトリプルを持っています。

つまり、考えられるすべてのトリプルをリスト順に単純に反復し、それらを並べ替えた順序で比較できます。この単純なソリューションは、漸近的に可能な限りすでに最高です (つまり、O(n^3))。

for (int i = 0; i < n; i++)
    for (int j = i+1; j < n; j++)
        for (int k = j+1; k < n; k++)
            if (X[i] < X[j] && X[j] < X[k)
                output(X[i],X[j],X[k])

問題文に転記ミスがあるのではないかと思います。そうでない場合、問題は非常に簡単で短いコーディング演習になるはずです。

于 2012-10-16T06:43:03.210 に答える
3

トリプルの小さなセット (k など) しかないことがわかっている場合は、前の最小要素へのポインターを格納して、すべてのトリプルを検索することをお勧めします。

アルゴリズム

空のデータ構造を準備します (可能な選択肢は後で説明します)。

長さ n の空の配列 B を準備します。

次に、リスト内の各要素 c について:

  1. データ構造を使用して、c (存在する場合) より小さいリスト内の最新の要素のインデックス (配列 B 内) を格納します。
  2. c (および元のリスト内のそのインデックス) をデータ構造に格納します
  3. 次に、配列 B を使用して c より小さいすべての要素 b を見つけ、次に b より小さいすべての要素 a を見つけて、これらすべての組み合わせを出力トリプルとして出力します。

データ構造

データ構造は、c より小さい値を持つすべての要素で最大の位置 (つまり、最新の位置) を簡単に見つけられるように、値と位置のペアを格納できる必要があります。

許容値の範囲がかなり小さい場合にこれを行う簡単な方法の 1 つは、A[k][x] が範囲 [x*2^k,(x+ 1)*2^k)。

値が最大 M ビット (つまり、値が 0 から 2^M-1 の範囲) の場合、このデータ構造の更新またはアクセスは両方とも O(M) 操作です。

複雑

与えられた方法は O(nM+k) です。

値の範囲が広い場合は、一連の配列の代わりにバイナリ検索ツリーの形式を使用するか、代わりに値を並べ替えて、値を序数値に置き換えることができます。この場合、複雑さは O(nlogn+k) になります。

トリプルを数える

この形式のトリプルの総数を知りたいだけの場合は、O(n) でこれを行うことができます。

考え方は以前と似ています:

  1. 各インデックスの最新の小さい要素と、各インデックスの小さい要素の数を見つけます
  2. 各インデックスの次に大きい要素と、大きい要素の数を見つける
  3. 各インデックスについて、小さい要素の数と大きい要素の数の積の合計を計算します。

これを O(n) にするには、O(n) 内で次に大きい要素を見つけることができる必要があります。これは次の方法で実行できます。

  1. 現在のインデックス i をスタックにプッシュする
  2. A[top(stack)] < A[i+1] の間、インデックス x をスタックからポップし、NGE[x]=i+1 を格納します
  3. i をインクリメントしてステップ 1 に戻る

また、O(n) 内のより大きな要素の数を見つけることができる必要があります。NGE 配列が準備されると、配列を逆方向に反復して計算することでカウントを見つけることができます。

count_greater_elements[i] = count_greater_elements[ NGE[i] ] + 1 if NGE[i] is defined
                          = 0 otherwise

最新の小さな要素とカウントは、同様の方法で計算できます。

于 2012-10-16T07:25:16.820 に答える
2

一般的な場合のN^2ソリューション（すべてを出力するのではなく、そのようなすべてのトリプルをカウントします。出力は、そのサイズのためにn ^ 3を取ります）：

配列内の各数値Xについて、インデックスがx未満のX未満の数値の量と、インデックスがXより大きいXより大きい数値の数をカウントできます。各Xよりも、Xが真ん中の要素であるトリプルの数を取得できます。 less [X] *great[X]として。答えはそのような製品の合計です。

int calc(vector<int> numbers) {
 int n = numbers.size();
 vector<int> less(n), more(n);
 for (int i = 0; i < n; i++)
  for (int j = i + 1; j < n; j++)
   if (numbers[i] < numbers[j])
    less[j]++, more[i]++;

 int res = 0;
 for (int i = 0; i < n; i++)
  res += less[i] * more[i];

 return res;
}
于 2012-10-16T17:28:00.913 に答える