6

次の問題を考えると、現在の質問に対する解決策がないため、修正をお願いします（教授の試験の1つから取得しました!!!）：

備考:これは宿題ではありません!

問題：

2 つの並べ替えられた配列A(with length n) & B(with length m) が与えられ、それぞれが

要素 (両方の配列内) は実数であり、数値X(これも実数) です。

が存在するかどうかを知りたいのですがa ∈ A、b ∈ B次のようになります。

a + b = X 、O(n+m)実行時間中。

解決 ：

より大きい数値は必要ないため、最初に両方の配列の末尾からチェックを開始しますX。

  • i = n

  • k = m

  • 一方 A[i] > X 、i = i -1

  • 一方、B[k] > X 、k = k -1

j = 0 を定義します。現在のiinAとin から実行を開始jしBます。

  • while i > 0 , j < k :
  • if A[i]+B[j] == X、次に両方のセルを返します
  • そうしないとj = j+1 , i = i -1

最終的に、2 つの要素が存在するか、配列の一方または両方が範囲外に到達するかのいずれかになります。これは、そのような要素が 2 つa + b = X存在しないことを意味します。

どんな発言でも大歓迎です

ありがとう

4

3 に答える 3

12

同時に調整iしないでください。j合計が大きすぎる場合は、減らす必要がありiます。小さすぎる場合は、 を増やしjます。

于 2012-06-27T14:32:32.580 に答える
4

この問題は、次の質問の特殊なケースです: O(log n) で並べ替えられた行列 (行 n 列) の数値を検索します。

で満たされた行列を考えてみましょうC[i,j] = A[i] + B[j]。次に、コーナーの 1 つから始めてi、合計が大きすぎる場合は減少し、小さすぎる場合は増加しjます。もちろんC、プログラムでこの行列を作成および/または入力する必要はありません。この行列の要素を知っていると仮定してくださいA[i] + B[j]。それは であり、いつでもすぐに計算できます。結果のアルゴリズムはO(m+n)です。

于 2012-06-27T14:35:09.830 に答える