2

私はこの問題に対する O(n 2 ) の解決策を持っており、より良い解決策があるかどうか疑問に思っています。合計が c である 2 つの数値を見つけようとしている場合、O(nlogn) の解があることがわかります。(ここで与えられます) ここで同様のアプローチを試します: 最初に O(nlogn) 時間でマージソートを使用して配列をソートし、次に配列の両端から開始して、それらの違いを調べます。これが c に等しい場合、完了です。差が c よりも大きい場合、右端のインデックスを 1 減らしますが、これは間違っていると思います。右端のインデックスを減らす必要があるのか​​、それとも左端のインデックスを増やす必要があるのか​​わかりません。私は正しいですか？この問題をより良い時間計算量で解けるでしょうか? ありがとう

4

3 に答える 3

4

重要なのは、配列がソートされると、二分探索はO(logn).

配列内の各数値について、 が配列内にあるかどうかを二分探索でxテストします。x-cこれはまだO(nlogn)です。

派手にしたい場合は、配列を 2 回反復するだけでそれを行うことができますが、いずれにせよ、複雑さは並べ替えステップによって支配されます。

于 2013-03-10T14:44:43.233 に答える
1

私のアプローチ、ハッシュとを使用してno need for pre-sorting、それはハッシュの実装に依存します。最良の場合はO（n）で実行でき、最悪の場合はO（nlogn）で実行できます。

arr[] = { ... }
hash[] // maps Integer to Boolean
for e in arr:
    hash[e] = true
    if hash[e+c] == true Or hash[e-c] == true:
        return true
return false

各要素に対して、配列を反復処理しeます。

  • eハッシュでtrueにマップ
  • 現在の要素との違いがある要素がある場合c、ビンゴ：D

お役に立てれば ：）

于 2013-03-10T15:17:19.297 に答える
0

O(n log n) 時間かかる配列をソートできます。次に、最初の各メンバー x を c - x に置き換えてから逆にすることで、2 番目の配列を作成できます。次に、2 つの配列に、それぞれ O(n) に対して 2 つの走査を行う共通の要素があるかどうかを確認できます。

于 2013-03-19T18:43:15.947 に答える