O（n）2つの配列に2つの要素があり、数字になるものがあるかどうかを調べる

Question

私は試験のために勉強していますが、少し難解です。

AまたはBの各要素がm = 0（n）の範囲0〜mにあるように、A [1 ... n]とB [1 ... n]を2の整数の配列にするとします。我々は二つの要素A [i]とB [j]は、その結果A [I] + B [jで見つけO（N）アルゴリズムを設計する必要（私はM < Nを意味すると仮定しています？）

] =与えられた数k。それらが存在しない場合は、エラーメッセージがスローされます。

ここで、ソートアルゴリズムがO（n lg n）なので、それらを並べ替えるのは問題になりません。

ハッシュテーブルを使用することもできます。あるいは、各インデックスがAの数値の出現をカウントするような長さmの小さな配列Xを作成してください。次に、Bを実行します.. calculate diff = k -B [j ] ...そしてあなたたちは

Answer 1

m = O(n)mは、必ずしもそれより小さいとは限らないnの定数倍である。あなたは何ができるか

はこれです。 （もO(n)であるので、メモリO(m)）サイズk+1の配列を取得します。この配列をCと呼んでください。すべての値をマークなしとして初期化します.1としましょう。これはO(m)であり、これもO(n)です。

k <= 2mは、A[i]とB[i]の両方が<= mであることがわかりました。だから配列A、Cにすべてk-A[i]のマークをつけていますので、k-A[i] >= 0とすると、から始まります。これはO(n)です。その後、配列Bを通過し、それぞれB[j]の場合は、C[B[j]]が既にマークされているかどうかを確認します。その場合、C[B[j]]は、Aの特定のインデックスには、B[j]+A[C[B[j]]] = kと印を付けます。 Bに行き、マークを確認することもO(n)です。一致するものが見つからない場合は、そのようなペアはありません。

全体アルゴリズムはO(n)です。

n = 5 
m = 15 
A = [1 7 4 2 10] 
B = [8 14 3 13 11] 
k = 20 

オーバーAを予定した後、あなたが得る：

C: [-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 4 -1 -1 1 -1 -1 2 -1 3 0 -1] 

（間隔がより良い視覚化のためである）そして、あなたはBに対してチェック：

B[0] -> C[8] -> -1 mismatch 
B[1] -> C[14] -> -1 mismatch 
B[2] -> C[3] -> -1 mismatch 
B[3] -> C[13] -> 1 match -> B[3] + A[1] = 20 

ここ

は一例です

B[3]は13およびA[1]は7であった。

Answer 2

をどう思いますか...それがゼロよりも大きい場合は、[はい、それは、その後、私たちはそのインデックスを見つけるために再び通過する可能性が存在します。..差分] [

をXをチェック最初の配列の各要素とその和の差を含むハッシュテーブルを使用します。基本的には、最初の配列を繰り返し処理し、配列の合計と各要素の差を計算し、ハッシュテーブルに格納します。次に、（あなたがちょうどあなた以来、しかし代わりに、int型のブール値を格納することができ、各番号はハッシュテーブル

Answer 3

に表示されている場合は、あなたが説明したハッシュテーブル法を用いて、（n）をOに並べ替えることができますチェックし、二番目の配列を反復処理それが存在するかどうかを知る必要がある）。一般的には、比較ソートはO（n個のLG N）よりも良いではないが、あなたは一定の制約を知っていれば（あなたは私はあなたがここにも使用することができると思う基数ソートなどの非比較ソート（）を使用できるかどうか）、あなたはより良い行うことができます。基本的に：

1. サイズnの配列A 'を初期化し、すべての値をfalseに設定します。
2. Aの各要素について、A 'の対応するインデックスをtrueに設定します。 Aの各要素に対して
3. 『」の値がtrueの場合、別の配列Aにインデックスを追加』。
4. A ''はソートされたAになり、重複が削除されました。 B.

問題の

繰り返しますが、AとBがソート持っていることを今非常に簡単でなければなりません。