与えられた数のセットについて
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)以下の時間でできるかどうか疑問に思っていました。
どんな助けでも大歓迎です。
O(n^2 * logn)
次の方法で達成できます。
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)
O(n^2)
中間の要素を選択してから、 の最初と最後の要素を選択することで、ハッシングを使用して解決できますO(n)
。
これは、合計が固定されている配列内の 2 つの数値を見つけるという単純な問題です。ここでは、 のa+c
はずです2b
。
したがって、私が探しているのはa
&c
そのようなものa+c=2i
です。