1

2 つの配列間で同じ数値を見つけるために、プログラムを作成する必要があります。問題は、いくつかの制約を考慮して、最も最適化された方法でそれを行う必要があることです:

- A[i]=B[w] および A[j]=b[x] および i の場合、配列 A の i,j インデックスと配列 B の w,x インデックスを持つ

-これらの数値間の最大距離は k でなければなりません (入力によって与えられます);

-検索を最適化するために何かを実装するには、最大で O(k) スペースを使用する必要があります。

-数字は各配列に 1 回だけ表示されます (セットのように)。

検索プロセスを最適化するために、最初の配列の k 個の要素を持つバランスの取れた RBTree を構築することを考えていましたが、必要なスペースについて疑問があります (ポインターとカラーマーキングのため、O(k) ではないと思います) ）。

誰でもこの問題についてより良い考えを持っていますか?

編集:より明確にするために、ここに例を示します。

  • 配列 A: 3 7 5 9 10 15 16 1 6 2
  • アレイ B: 4 8 5 13 1 17 2 11
  • 定数 k = 6
  • 出力: 5 1 2

Edit2: 出力では、数値は配列内と同じ順序で表示される必要があります。

4

1 に答える 1

0

K を最大距離として使用

配列の順序で表示する必要があると言うとき、1 つの配列からの順序で十分であると仮定すると、次のようになります。

A: 1 2 B: 2 1

順序が交差しているため、結果は 1 2 または 2 1 になり、1 または 2 のいずれにもなりません

K制約により、これが最適でなくなることに注意してください

最初の観察は、小さい方の配列内の要素数のインデックス + K -1 を超える大きい方の配列内のものは無視できることです。

2 番目の観察は、すべての値が明らかにint

3 番目の観察は、配列のサイズに近い可能性がある K を持つ巨大な配列に最適でなければならないということです。

基数ソートは O(N) で、O(N) サイズを取るので、それを使用します

K を許可するために、両方の配列を (値、位置) の並列配列にコピーし、観察 1 に従って大きな配列では到達できない値をコピーしないようにすることができます。つまり、A: 71, 23, 42 ==> A2: { 71 , 0 }, { 23, 1 }, { 42, 2 }

小さい方の配列と同じサイズの結果用の同様の配列を作成することもできます

基数ソートを変更して、値と位置を一緒に移動できます

アルゴリズム:

1) Copy arrays [ O(1) ]

2) Radix sort array A and B by values [ O(1) ]

3) Walk A and B: [ O(1) ]
if A < B -> increment index in A
if A > B -> increment index in B
if A == B -> incremnt index in A and B
             add original A to result IF the pos diffence is less than K    
4) Radix sort results by position [ O(1) ]

5) print result values [ O(1) ]
于 2013-11-14T03:27:46.597 に答える