最後に更新されたときにタイムスタンプのマークが付いたオブジェクトの配列があります。最近更新された項目のみを含む配列のサブセットを取得したいと考えています。50 から 100 の配列から 5 つの要素のみを取得します。パフォーマンスが最優先事項であるため、クラス メソッドの 1 つを使用して配列全体を並べ替える必要があります。これを行う最善の方法は何ですか？
2 に答える
1
必要な数の要素を選択したら、挿入ソートを使用してブレークアウトします。このソリューションの複雑さはO（k * n）です。ここで、kは抽出される要素の数です。
O（n）のソートされていない配列でK番目に大きい要素を見つけるアルゴリズムもあります。
O（n）の長さnのソートされていない配列でk番目に大きい要素を見つける方法は？
K番目に大きい要素Xを見つけたら、配列をトラバースして、Xより大きいすべての要素を選択できます。Xよりも正確にk-1個の要素があることが保証されます。
于 2012-06-02T04:32:54.860 に答える
0
要素が 100 個しかない場合は、単純に並べ替えます。それ以外の場合は、ヒープ ベースのプライオリティ キューの実装を使用します。O(n) を作成すると、それ以降のすべての挿入/削除には O(logn) コストが関連付けられます。
于 2012-06-02T05:40:44.327 に答える