15

次の問題を検討してください。

ソートされていない整数の配列を指定して、x^2 + y^2 = z^2 を満たすすべてのトリプレットを見つけます。

たとえば、指定された配列が1, 3, 7, 5, 4, 12, 13の場合、答えは と である必要が5, 12, 13あります。3, 4, 5

複雑さ O(n^2) の以下のアルゴリズムをお勧めします。

  • 配列を降順に並べ替える O(nlogn)
  • 各要素の二乗、O(n)

ここで、a = b+c となるようにソートされた配列内のすべてのトリプレット (a、b、c) を見つける問題に還元されます。

インタビュアーは、O(n^2) よりも優れたソリューションを主張していました。

ウィキペディアで 3SUM 問題を読みました。これは、配列がビット ベクトルとして表現できると仮定して、数値が [-u,u] の範囲内にある場合、O(n+ulogu) で問題を解決できることを強調しています。しかし、それ以上の説明を明確に把握することはできません。

誰かが良い例で何が起こっているのかを理解するのを手伝ってくれませんか?

4

2 に答える 2

7

別の可能性 (インタビュアーの心を誰が理解できるでしょうか?) は、方程式を次のように書き直すことです。

 x^2 + y^2 = z^2
 x^2 = z^2 - y^2 = (z-y)(z+y)

x^2 の素因数分解がわかっている場合、考えられるすべての因数分解を単純に反復して、数値 p,q (p < q) のペアにし、計算することができます。

 x^2 = p.q = (z-y)(z+y)
 p+q = (z-y)+(z+y) = 2z
 q-p = (z+y)-(z-y) = 2y
 z = (p+q)/2
 y = (q-p)/2

したがって、因数分解 x^2=pq が与えられると、z と y の値を計算できます。すべての整数値をセットに入れることで、それらの z、y 値が配列内にあるかどうかを確認することで (チェックごとに) 時間 O(1) で可能な各回答をチェックできます (負の値も検出されることに注意してください)。 .

ウィキペディアによると、ランダムに選択された整数にはおよそ log(n) の約数があるため、素因数分解を十分に高速に実行できると仮定すると、約 n.log(n) かかるはずです (たとえば、すべての整数が 100 万未満であることがわかっている場合は、配列を事前計算できます)。各整数の最小係数の)。

于 2012-06-12T20:02:25.977 に答える
7

初めに。最悪の場合、すべてのトリプレットを見つけることはO(n^3)です。数字があるとしますn=3k。それらのうちの K は 3、k は 4、k は 5 です。

3,....,3,4,....,4,5,.....5

k^3 = n^3/27 = O(n^3)そのような三つ子があります。印刷するだけO(n^3)でも時間がかかります。

次に、このような形式で 3SUM 問題を説明します。

s_1, ..., s_nそれぞれの範囲に数字があります[-u;u]。トリプレットa,b,cはいくつありa+b=cますか?

  1. 変身中。2*u の数字を取得しますa_-u, ..., a_0, a_1, ... a_ua_iは数量s_j、それs_j = i。これはで行われますO(n+u)

  2. res = a_0 * sum(i=-u..u, i=/=0, C(a_i, 2)) + C(a_0,3) a_0 = 0

  3. 多項式を構築しP(x) = sum(i = -u...u, a_i*x^(i+u)ます。

  4. FFTQ(x) = P(x)*P(x)を使用して検索します。

  5. ここでQ(x) = sum(i=-2u..2u, b_i*x^(i+2*u))b_iは ペアの数 でs_uあることに注意しs_kてくださいs_u+s_k = i(これには、同じ数を 2 回使用することも含まれます)。

  6. すべての場合iでもb_i = b_i - a_(i/2)。これにより、同じ番号を 2 回使用して削除されます。

  7. すべて合計b_i*a_i/2- これを res に追加します。

例:より単純にするために、数値の範囲は [0..u] であり、x のべき乗で +u を使用しないと仮定します。数字があるとします1,2,3 -a_0 = 0, a_1 = 1, a_2 = 1, a_3 = 1

  • res = 0

  • P(x) = x + x^2 + x^3

  • Q(x) = x^2 +2x^3+3x^4+2x^5+x^6

  • 引き算後b_2 = 0, b_3 = 2, b_4 = 2, b_5 = 2, b_6 = 0

  • res += 0*1/2 + 2*1/2 + 2*0/2 + 2*0/2 + 6*0/2 = 1

于 2012-06-11T10:42:11.340 に答える