次のデータ構造の質問を考えています。
1との間の整数を指定nすると、すべての操作でクエリが実行され、(1 回の呼び出しで)k最小の数値が削除されます。クエリと削除の両方を一定時間の操作にする方法は?
これは配列構造に似ていますが、定数の削除が必要です。順序のバランスがとれた二分木はこれを行うことができますが、O(lg n)複雑です。
range プロパティ (1との間の数値のみn) を利用して機能させることはできますか?
質問する
176 次
2 に答える
1
の最大値はN? あなたは正の数で作業しようとしていると述べました.Van Emde Boasツリーはおそらくあなたにとって最良の選択です.
簡単な説明:
- [0,2^k) の正の数のみを格納できます。ここで、k は最大数を格納するために必要なビット数Nです。
- すべての操作 (insert、delete、lookup、find_next、find_prev) は で機能しlog(K)ます。log(N) ではありません。したがって、整数の 32 ビット数の複雑さは log(32)=5
です。欠点はメモリ消費です。には2^k ~ O(N)メモリが必要なため、整数を格納するには最大 1GB の RAM が必要です。通常、O(N) メモリは O(要素数) を意味しますが、ここでは O(最大格納値) を意味します。
注: k 番目の要素クエリのサポートについてはわかりませんが、説明は良さそうです:
FindNext: 少なくとも指定された k で最小のキーを持つキーと値のペアを見つけます
FindPrevious: 指定された k 以下で最大のキーを持つキーと値のペアを検索します
アップデート
Dukeling が後述するように、K 番目の要素のクエリはサポートされていません。私はそれを実装する唯一の方法を見ています。
int x = getMin();
for(int i=0;i<k-1;i++) x = getNext(x);
このループの後、x は k 番目の要素を格納します。しかし、複雑さはO(K*log(bits)). K( の値が大きいのは残念
于 2013-10-31T05:02:07.230 に答える
1
LinkedHashSetはあなたが探しているものです。配列のようにインデックスが必要な場合は、このLinkedHashMapを使用してください。1しかし、それらを順番に挿入する必要がありますn
于 2013-10-30T17:51:02.760 に答える