これは私がウェブ上で見つけた興味深い質問です。数値を含むn(数値に関する情報を持たない) 配列が与えられた場合、線形時間で配列を前処理して、数値が与えられたときkに時間内に最小の要素を返すことができるようにする必要があります。O(k)1 <= k <= n
この問題について何人かの友人と話し合っていますが、誰も解決策を見つけることができませんでした。どんな助けでも大歓迎です！
1295 次
2 に答える
15
前処理ステップでは、同じデータ セットに対してパーティション ベースの選択を数回使用します。
アルゴリズムを使用してn/2番目の数値を見つけます。これで、データセットは下半分と上半分の 2 つに分割されました。下半分で再び中間点を見つけます。その下のパーティションで同じことを行います...全体として、これは O(n) + O(n/2) + O(n/4) + ... = O(n) です。
k 個の最小要素を返す必要がある場合は、最も近いx < kを検索します。ここで、xはパーティションの境界です。それより下のすべてを返すことができ、次のパーティションからはk - xの数値を返す必要があります。次のパーティションのサイズはO(k)であるため、 k - x番目の数値に対して別の選択アルゴリズムを実行すると、残りが返されます。
于 2013-06-23T14:52:59.890 に答える