最初に、 kが実際に乱数である場合、問題が完全に異なる可能性があることを考慮する価値があるかもしれないことを指摘したいと思います。k番目に小さい要素を求め、kは使用可能な要素の範囲で均一にランダムになります。基本的に...要素をランダムに選択します。そして、それは非常に異なる方法で行うことができます。
ここでは、任意の場合でも、特定のkを実際に選択する必要があると想定しています。
要素が順番に挿入されるという強い前提条件を考えると、簡単な解決策があります。
- 要素は順番に指定されているので、配列に1つずつ追加するだけです。つまり、いくつかの(無限の)テーブルTと、カーソルc(最初はc:= 1)があり、要素を追加するときに、T [c]:= xおよびc:= c+1を実行します。
- k番目に小さい要素にアクセスする場合は、T[k]を見てください。
もちろん、問題は、要素を削除すると、テーブルにギャップが作成され、要素T [k]がk番目に最小ではなく、j<=kでj番目に最小になる可能性があることです。 kの前のセルは空です。
次に、削除した要素を追跡し、kよりも小さい要素がいくつ削除されたかを知るだけで十分です。せいぜいO(log n)でこれをどのように間に合わせるのですか?範囲ツリーまたは同様のタイプのデータ構造を使用する。範囲ツリーは、整数を追加してから、 XとYの間のすべての整数を照会できる構造です。したがって、アイテムを削除するときはいつでも、範囲ツリーに追加するだけです。そして、k番目に小さい要素を探しているときは、削除された0からkまでのすべての整数に対してクエリを実行します。そのデルタを言うが削除されている場合、k番目の要素はT [k+delta]になります。
わずかな問題が2つあり、修正が必要です。
範囲ツリーは時間O(log n)の範囲を返しますが、範囲内の要素の数をカウントするには、範囲内の各要素をウォークスルーする必要があるため、時間O(D)が追加されます。ここでDは範囲内のアイテムを削除しました。これを取り除くには、範囲ツリー構造を変更して、各ノードでサブツリー内の個別の要素の数を追跡する必要があります。このカウントを維持するのにかかる費用はO(log n)のみであり、全体的な複雑さには影響しません。これを行うのはかなり簡単な変更です。
実際には、クエリを1つだけ作成しても機能しません。実際、1からkの範囲でデルタ削除された要素を取得する場合は、k+1からk+deltaの範囲で削除された要素がないことを確認する必要があります。完全なアルゴリズムは、以下の内容に沿ったものになります。
KthSmallest(T,k) := {
a = 1; b = k; delta
do {
delta = deletedInRange(a, b)
a = b + 1
b = b + delta
while( delta > 0 )
return T[b]
}
この操作の正確な複雑さは、削除をどの程度正確に行うかによって異なりますが、要素がランダムに均一に削除される場合、反復回数はかなり少なくする必要があります。