与えられた数のセットについて
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）以下の時間でできるかどうか疑問に思っていました。
どんな助けでも大歓迎です。
2208 次
2 に答える
5
O(n^2 * logn)次の方法で達成できます。
- 配列を並べ替える - O(nlogn)
- すべてのペア (それらの 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 に答える