重複の可能性：
タプルの数
N個の数a[1..N]と他の2つの整数LとHが与えられた場合、。の(i,j,k)ようなタプルの数を数える必要がありL <= a[i] + a[j] + a[k] <= Hます。これはより良い方法で行うことができますO(n^3)か？提案/アルゴリズムはありますか？
1038 次
1 に答える
0
最初に a[i] を昇順に並べ替えます。
a[i] と a[j] を列挙すると、二分探索を使用して L - (a[i] + a[j]) <= a[k] <= H - ( a[i] + a[j])。
アルゴリズム全体のコストO(n^2*log(n))
于 2012-11-04T08:39:03.930 に答える