0

Javaでは、順序付けられていない数字のコレクションからO(n)時間で逆順でPriorityQueueを作成する簡単な方法はありますか? PriorityQueue のコンストラクターは、コレクションとコンパレーターの両方を使用して順序を指定するものはありません。コンパレータを指定して PriorityQueue を作成し、後で addAll を呼び出して、順序付けされていないすべての番号を追加できることはわかっています。ただし、順序付けされていないコレクションをヒープ化するのではなく、 addAll が各値を個別に追加すると思うので、O(n) 時間になるとは思いません。

4

2 に答える 2

0

回避策は、最初に数値を否定してから、O(n) でそれらからヒープを作成することです。後で、ヒープから数値を取得した後に数値を否定することを忘れないでください。

于 2012-11-28T01:00:38.923 に答える
0

addAll の複雑さは O(n*log(n)) であるため、それほどひどいものではありません。

番号の順序付けられていないコレクションから PriorityQueue を作成すると O(n) になるという考えをどこで得たのかわかりませんが、addAll の場合と同じだと思います。

于 2012-11-28T00:48:49.513 に答える