5

正の整数のシーケンスと整数 M を指定すると、シーケンス内で M (存在しない場合は -1) より大きい最初の数値を返します。

例: シーケンス = [2, 50, 8, 9, 1]、M = 3 -> リターン = 50

必要なクエリごとに O(log n) (前処理後)。

私はBSTについて考えましたが、昇順のシーケンスを考えると、長いパスしか得られず、O(logn)時間は得られません...

編集: 使用される構造も変更が容易である必要があります。つまり、見つかった要素をその特定の要素に置き換えて、別の M (前処理を除くすべて - O(logn)) の検索を繰り返すことができる必要があります。そしてもちろん、「最初に大きい」を「最初に小さい」に変更でき、アルゴリズムをあまり変更する必要がなかったとしたら、それは素晴らしいことです。それが役に立てば、すべての数は正であり、繰り返しはないと仮定できます。

4

1 に答える 1

10

2 番目の配列を作成します (それを としますaux)。ここで、各要素についてi: aux[i] = max { arr[0],arr[1], ... ,arr[i]}(元の配列内のインデックスを持つすべての要素の最大値j <= i)。

この配列が本質的にソートされていることは簡単にわかります。単純なバイナリ検索auxにより、必要なインデックスが得られます。(要素が存在しない場合、要求された要素よりも大きい最初の要素をバイナリ検索で取得するのは簡単です)。

時間の複雑さは、O(n)前処理 (1 回だけ実行) とO(logn)クエリごとです。

于 2012-12-08T18:17:23.973 に答える