4

与えられた数のセットについて

3 5 3 6 3 4 10 4 5 2

**triplets**等差数列を形成するをすべて見つけたいです。

like (3,3,3) (3,4,5) (6,4,2) (3,4,5)

私は簡単な O(n^3) ソリューションを持っています。O(n ^ 2)以下の時間でできるかどうか疑問に思っていました。

どんな助けでも大歓迎です。

4

2 に答える 2

5

O(n^2 * logn)次の方法で達成できます。

  1. 配列を並べ替える - O(nlogn)
  2. すべてのペア (それらの O(n^2)) を反復処理し、各ペア (x,y) についてバイナリ検索を実行して、要素としてmax{x,y} + abs(x-y)orがあるかどうかを確認しますmin{x,y} - abs(x-y)
    -のペアには特別な注意を払う必要がありx==yますが、同じ時間の計算量内で簡単に解決できます。

このソリューションでは、各トリプレットが 1 回出現することに注意してください (重複なし)。

編集:配列をソートしてバイナリ検索を使用する代わりに、ハッシュテーブル(トリプレットの数を気にする場合はヒストグラムO(n^2))を使用してそれを調べます-追加のスペースのコストで、平均して時間を短縮できますO(n))。


1 出現の欠点がなければ、たとえば配列内にそのようなトリプレットO(n^3)が存在する可能性があるため、それよりもうまく行うことはできません。そのようなトリプレットがあります。O(n^3)[1,1,1,...,1]chose(3,n)

于 2012-11-10T09:14:12.807 に答える
1

O(n^2)中間の要素を選択してから、 の最初と最後の要素を選択することで、ハッシングを使用して解決できますO(n)

これは、合計が固定されている配列内の 2 つの数値を見つけるという単純な問題です。ここでは、 のa+cはずです2b

したがって、私が探しているのはa&cそのようなものa+c=2iです。

于 2015-09-16T14:31:23.393 に答える