2

基本的に、ペアを格納し、値によって要素の上位 N 数を取得できる Java で最適なデータ構造を探しています。これを O(n) 時間で実行したいと思います。ここで、n はデータ構造内の整数の数です。

入力例は、

<"john", 32>
<"dave", 3>
<"brian", 15>
<"jenna", 23>
<"rachael", 41>

N=3 の場合、降順で並べ替えたい場合は、rachael、john、jenna を返すことができるはずです。

ある種の hashMap を使用すると、挿入は高速ですが、順番に取得するとコストがかかります。順序付けを維持するデータ構造を使用すると、挿入が高価になり、取得が安価になります。非常にうまくかつ非常に高速に実行できる最適なデータ構造を見つけることができませんでした。

どんな入力でも大歓迎です。ありがとう。

[更新しました]

それがより明確になる場合は、別の方法で質問させてください。私は一定の時間に O(1) を hashMap に挿入できることを知っています。さて、O(n)時間で値によってソートされた順序から要素を取得するにはどうすればよいですか?ここでn=データ構造内の全体の数? それが理にかなっていることを願っています。

4

1 に答える 1

5

並べ替えたい場合は、一定の O(1) 時間をあきらめる必要があります。

これは、ソートされていないキーと値のペアを挿入する場合とは異なり、ソートでは新しいエントリを何かと比較する必要が最小限であり、オッズはいくつかのものと比較されるためです。(より多くの比較のために) より多くのエントリでより多くの時間を必要とするアルゴリズムを取得すると、「一定の」時間を超過したことになります。

もっと上手にできるなら、ぜひそうしてください！フィールズ賞ではないにしても、ダイクストラ賞があなたを待っています。

失望しないでください。キー部分を HashMap として実行し、ツリーのような実装で並べ替え部分を行うことができます。これにより、O(log n) が得られます。TreeMap はおそらくあなたが望むものです。

--- アップデートに合わせてアップデート ---

いいえ、O(n) 時間でハッシュマップを反復処理することはできません。これを行うには、リストがあると仮定します。ただし、そのリストは既にソートされている必要があります。生の HashMap を使用すると、マップ全体で次の「低い」値を検索する必要があります。チェックしなかった 1 つの要素が正しい値である可能性があるため、マップの一部を検索することはできません。

現在、多くのトレードオフを行ういくつかのデータ構造があり、それがあなたを近づけるかもしれません. 独自のヒープを作成したい場合は、おそらくカスタム フィボナッチ ヒープを使用すると、希望するパフォーマンスに近い償却パフォーマンスを得ることができますが、最悪の場合のパフォーマンスを保証することはできません。いずれにせよ、一部の操作 (extract-min など) では、O(log n) のパフォーマンスが必要です。

于 2013-09-24T01:39:59.763 に答える