8

これは私がオンラインで見たインタビューの質問であり、私はそれについて正しい考えを持っているかどうか確信が持てません.

問題はここにあります：

n 個の数列から最大の 2 つの要素を見つけるアルゴリズムを設計します。比較の数は n + O(log n) である必要があります

2 つの最大の要素が見つかったら、クイック ソートを選択して停止することができると思いますか? しかし、それについて 100% 確信があるわけではありません。誰でもそれについてアイデアを共有してください

4

2 に答える 2

15

配列を再帰的に分割し、それぞれの半分で最大の要素を見つけてから、最大の要素がこれまでに比較された最大の要素を見つけます。その最初の部分では n 回の比較が必要であり、最後の部分では O(log n) が必要です。次に例を示します。

1 2 5 4 9 7 8 7 5 4 1 0 1 4 2 3
2   5   9   8   5   1   4   3
5       9       5       4
9               5
9

各ステップで、隣接する数値をマージし、2 つのうち大きい方を取得します。最大の数である 9 に到達するには n 回の比較が必要です。次に、9 が (5, 5, 8, 7) と比較されたすべての数を見ると、最大のものは 8 であることがわかります。配列で 2 番目に大きい。これには O(log n) のレベルがあるため、これを行うには O(log n) の比較が必要です。

于 2012-05-14T21:33:46.163 に答える
1

最大の要素が2つしかない場合は、通常の選択で十分な場合があります。基本的にはO（2 * n）です。

より一般的な「配列サイズnからk個の要素を選択する」質問の場合、クイックソートは良い考えですが、実際に配列全体をソートする必要はありません。

これを試して

  1. ピボットを選択し、配列をN[m]とN[nm]に分割します。
  2. k <mの場合、N [nm]の部分を忘れて、N[m]でステップ1を実行します。
  3. k> mの場合、N [m]の部分を忘れて、N[nm]でステップインします。今回は、N[nm]の最初のkm要素を見つけようとします。
  4. k = mの場合、あなたはそれを手に入れました。

これは基本的に、配列Nでkを見つけるようなものです。log（N）の反復が必要であり、平均して（N / 2）^i要素を移動します。したがって、これはN + log（N）アルゴリズム（要件を満たします）であり、非常に優れた実用的なパフォーマンスを備えています（ソートを回避するため、出力は順序付けられないため、単純なクイックソートよりも高速です）。

于 2012-05-15T04:56:34.740 に答える