2

説明：

n 個の正の整数で構成される配列が与えられた場合、C=A+B となる最大の C を見つけます。A、B、C はすべて指定された配列にあります。

例：

1 1 1 4 5 5 6 6 10 9 C=10

1 3 6 C=-1, これは最大の C が存在しないことを意味します

O(n^3) 未満のアルゴリズムを探しています。どなたか教えていただけないでしょうか?

4

3 に答える 3

7

リストを並べ替えます。C を最大から最小に繰り返し、B を最小から C の値に繰り返します。これまでのところ、それは O(n^2) です。(C, B) のペアごとに A を計算し、それが配列内にあるかどうかを確認するだけです。O(n^2 log n) の全体時間に対して二分探索を使用できます。

于 2013-01-29T04:08:57.663 に答える
0

@valtron のアルゴリズムに基づいて O(n^2) で十分です

于 2013-01-29T05:07:22.600 に答える