2

ソートされていない整数配列と、0 <= i <= j <= C (定数は MAX_INTEGER と言う) となるような 2 つの数値 i と j が与えられた場合、その数値を見つけるためにどのような前処理を実行できるかo(1) 時間での i と j (両方を含む) の間の数。配列は重複することもあります。

私は、配列内の要素（空間o（C））の頻度配列f []と、累積頻度（空間o（C））の別の配列cf []を構築することを考えていました。

したがって、i と j が与えられた場合、累積頻度配列を検索して cf[j] - cf[i] を実行できます。これにより、i と j の間の要素の数が得られます。i と j を含めるには、頻度配列を調べて値を追加します。すなわち cf[j] - cf[i] + f[i]+f[j] 時間の計算量は o(1) * 4 = 定数時間になります。

周波数配列でのルックアップは、それぞれの方向の i と j の両方について前の非ゼロ cf 配列要素を見つけることで回避できます。これにより、時間の複雑さが増しますが、空間の複雑さが軽減されます。

この問題に対するより良い解決策があるかどうか知りたいです。

注 - i と j の値は、前処理が完了した後にのみ使用できます。

-ビジェイ

4

4 に答える 4

-1 
Dim result() as integer
Dim C(1000) as integer
Dim Buff() as integer
Dim i as integer=50 
dim j as integer=450 
for count =0 to c.count-1
    if c(count)>i and c(count)<j then 
       dim length as integer=buff.count-1
       redim result(lenght+1)
       for buffcount=0 to buff.count
           result(buffcount)=buff(buffcount)
       next  
       result(result.count-1)=c(count)
       redim buff(result.lenght-1)
       buff=result
    end if 
next
于 2013-07-26T14:31:47.737 に答える