5

これはインタビューの質問です。

整数の配列と間隔のストリーム(整数のペア) を指定して、ストリームの各間隔に該当する配列の要素を見つけます。どの配列前処理を使用しますか?

4

4 に答える 4

9

1 つのオプションは、配列を昇順に並べ替えて前処理することです。これが完了すると、ソートされた配列に対して 2 つのバイナリ検索を実行することで、間隔内にあるすべての要素を見つけることができます。間隔の終点を超えない - 次に、配列全体を反復処理して、その範囲内のすべての要素を出力します。

クイックソートやヒープソートなどの標準的なソート アルゴリズムを使用する場合、前処理に O(n log n) の時間が必要ですが、基数ソートを使用する場合は O(n log U) の時間で実行できます (ここで、U は最大の整数です)。範囲）。次に、クエリにはそれぞれ O(log n + k) の時間がかかります。ここで、n は要素の数、k は範囲内の要素の数です。

凝りを加えたい場合は、整数を格納するための特殊なデータ構造であるvan Emde Boas ツリーを使用することで、これを指数関数的に高速化できます。使用している最大の整数値が U の場合、時間 O(n log log U) で構造を構築し、時間 O(log log U) でエンドポイント範囲検索を実行できます。次に、範囲内のすべての要素を時間 O(log log U) でそれぞれ見つけることができ、範囲内のすべての一致を見つけるための O(k log log U) アルゴリズムを提供します。

お役に立てれば！

于 2013-02-16T18:24:33.110 に答える
3

答えは要件によって異なります。

M と言う間隔はいくつありますか?

もちろん、 M * O(N logN) を使用するのは過剰です。特に M が大きく、 interval も大きい場合はそうです。

別のアプローチ: O(N) 余分なスペースを使用します。 

prefix[i] = number of numbers in range 0 to i

O(N) 時間で実行できます。

ここで、クエリごとに O(1) 時間が必要です。 

query[l,r] = prefix[r] - prefix[l - 1] + 1

したがって、合計時間の複雑さはO(N logN + M)

于 2014-02-11T13:55:47.600 に答える
3

配列をソートし、二分探索を実行して間隔開始よりも大きい配列内の最初の要素のインデックスを見つけ、次に再び間隔終了よりも小さい最初の要素を見つけ、その間のすべての整数を返します。 . O(log N)Nが整数の数であるルックアップごとになります。

于 2013-02-16T18:25:40.320 に答える
1

その要素に従って配列にインデックスを付けるのはどうですか?

for (i in original_array) indexed_array[original_array[i]] = original_array[i]

for (j in stream) {
  for (k=stream[j][0]; k<=stream[j][1]; k++) 
    if (indexed_array[k]) return indexed_array[k]
}

または、整数の代わりにインデックスを配置します。

for (i in original_array) indexed_array[original_array[i]] = i
于 2013-02-16T20:11:38.540 に答える