2

与えられた n 要素の配列の要素を並べ替えて、そのすべての負の数がすべてのゼロに先行し、すべてのゼロがすべての正の数に先行する線形アルゴリズムを設計します。また、一定量以上の追加スペースを必要としないように、スペース効率も高くする必要があります。

私が考えているものはすべて よりもはるかに大きく、O(n)いくつかのヒント/ヒント/ヘルプ/Java コードが大好きです!

4

3 に答える 3

2

ヘルプ?ヒント: クイックソートのパーティション部分をピボットとして0. このウィキペディアの記事を参照して、インプレース バージョンを探してください。


上記のリンクで指定された正確なバージョンを実装しても、重複がゼロの場合は役に立たない可能性があることに気付きました。クイックソートのパーティション部分を使用する必要があるという私の声明は依然として真実ですが、パーティションはオランダ国旗問題または 3 方向のパーティション分割によって行われます。ここにあなたのための疑似コードがあります

//インデックスベース 1 と仮定
A[1..n]
p = 0
q = n+1
私は= 1
i < q の間 A[i] < 0 の場合 スワップ(i, ++p) それ以外の場合 A[i] > 0 スワップ (i, --q) そうしないと i++

時間の複雑さ:    O(n)
空間の複雑さ:O(1)

于 2012-10-22T04:59:51.473 に答える
2

Radix Sort の修正版の使用を検討してください。線形時間で機能する唯一のソートは非比較ベースのソートです (したがって、リスト/配列内のエントリは互いに比較されません)。アイテムを比較する並べ替えが常に少なくとも nlogn になる理由については、最小の高さの比較ツリーを参照してください)。

于 2012-10-22T04:59:54.457 に答える
1

負のゼロと正の 3 つの範囲に従って項目の再配置のみが必要な場合。

簡単な解決策は、単一の配列反復 (O(n)) で負、ゼロ、および正の項目の数を数えることです (実際、配列のサイズが既にわかっている場合は、正の数を数える必要はありません)。

2 回目の反復では、適切な index までの範囲に従って項目を (最初の項目から開始して) 交換し、次に index を増やします。

それだけです。追加のメモリや teta(n) 時間の複雑さはありません。

于 2012-10-22T09:02:37.307 に答える