1

structsという配列がありstruct Test testArray[25]ます。

には、というTest structメンバーが含まれていint sizeます。

Test structsmember に基づいて、元の 5 つの最大のものを除くすべてを含む別の配列を取得する最速の方法は何sizeですか? 元の配列を変更せずに。

注: 配列内の項目の量は、はるかに大きくなる可能性があります。これをテストに使用しただけで、値が動的になる可能性があります。テスト用に遅いサブセットが欲しかっただけです。

オリジナルのコピーを作成してから、testArrayその配列をソートすることを考えていました。Test structs次に、 (asc または desc に応じて) 上位 5 または下位 5 を含まないの配列を返します。

また

最大の 5 を探して反復しtestArray、最大の 5 を除いて元の配列のコピーを作成します。この方法では、見つかった最大の 5 つの配列と比較して、配列を反復する回数が多すぎるようです。

フォローアップの質問:

これが私が今していることです。あなたの考えを教えてください。

関心のある最大の要素の数が同じままであることを考慮して、配列を反復処理し、最大の要素を取得して配列の前にスワップしています。次に、最初の要素をスキップして、その後で最大のものを探し、それを 2 番目のインデックスに交換します。最初の 5 つが最大になるまで。次に、並べ替えを停止し、6 番目のインデックスを最後まで新しい配列にコピーします。

このように、何があっても、配列を 5 回だけ反復します。そして、私はすべてをソートする必要はありません。

4

4 に答える 4

3

線形時間選択アルゴリズムを使用した部分ソートは、これをO（n）時間で実行します。ここで、ソートはO（nlogn）になります。

部分的な並べ替えページを引用するには：

上記の線形時間選択アルゴリズムを使用して、最悪の場合の線形時間O（n）でk個の最小要素またはk個の最大要素を見つけることができます。k個の最小要素を見つけるには、線形時間の中央値の中央値選択アルゴリズムを使用して、k番目に小さい要素を見つけます。その後、k番目に小さい要素をピボットとして配列を分割します。k個の最小要素が最初のk個の要素になります。

O（n）でk個の最大のアイテムを見つけることができますが、配列または各要素へのポインターの配列（よりスマート）を作成すると時間もかかりますが、それでもそれを行う必要があります。

関連するアルゴリズムの完全な説明を希望する場合は、コメントしてください。

更新： フォローアップの質問については、基本的にリストを5回繰り返すことをお勧めします...それでうまくいきます。ただし、必要以上にリストを繰り返し処理します。（O（n）選択アルゴリズムを使用して）1回のパスでk個の最大要素を見つけることは、それよりもはるかに優れています。このようにして、新しい配列を作成するために1回繰り返し、選択を行うためにもう一度繰り返します（中央値の中央値を使用する場合は、作業を分割するだけでよいため、最大の5つの項目を削除するために3回繰り返す必要はありません。新しい配列を作成するために1回繰り返してから、さらに5回繰り返すのではなく、5番目に大きいアイテムがどこにあるかに基づいて2つの部分に配列します。

于 2013-02-07T21:40:25.117 に答える
0

たぶん、配列はあなたが望むものに最適な構造ではありません. 特に、新しい値が追加されるたびに並べ替える必要があるためです。おそらく、リンクされたリストの方が優れており、挿入時の並べ替え (最悪の場合は O(N)、最良の場合は O(1)) を使用してから、最後の 5 つの要素を破棄するだけです。また、ポインタを切り替えるだけで、配列全体を再割り当てしてそこに別の要素を取得するよりもかなり高速であることを考慮する必要があります。

AVL ツリーではないのはなぜですか? トラバース時間は O(log2N) ですが、ツリーのバランスを取り直す時間を考慮する必要があります。

于 2013-02-07T21:57:38.033 に答える
0

述べたように、ソートは O(nlogn +5) O(5n + 5) で繰り返されます。一般に、m 個の最大数を見つけることは、ソート アルゴリズムを使用して O(nlog +m) になり、反復アルゴリズムで O(mn +m) になります。どちらのアルゴリズムが優れているかは、m と n の値によって異なります。値が 5 の場合、最大 2 から 5 番目の数値、つまり 32 までは反復の方が優れています。ただし、操作に関しては、並べ替えは反復よりも集中的であるため、高速になるまではかなりの時間がかかります。

これまでの最大数の並べ替えられた sray とバイナリ検索を使用して O(nlogm) が得られる順序を維持することで、理論的にはより適切に実行できますが、これも n と m の値に依存します。

于 2013-02-07T21:43:16.700 に答える
0

データ構造を使用しmin-heapてヒープ サイズを に設定する5と、ヒープの最小要素が配列内の要素よりも小さい場合に、配列をトラバースしてヒープに挿入できます。 getMin時間がかかりO(1)、挿入にO(log(k))時間がかかります。kはヒープの要素サイズです (この場合は です5)。したがって、最悪の場合、O(n*log(k))最大 5 つの要素を見つけるのが複雑になります。O(n)除外リストを取得するには、別の方法が必要です。

于 2013-02-07T22:46:35.250 に答える