これは面接の質問です。ソートされた整数配列と数値zが与えられた場合、x + y <zとなるように、配列内のすべてのペア（x、y）を見つけます。O（n ^ 2）よりもうまくできますか？
PS O（N）ですべてのペア（x、y | x + y == z）を見つけることができることを私は知っています。
質問する
1602 次
7 に答える
9
このプロパティを持つ値のO（n 2 ）ペアが存在する可能性があるため、必ずしもO（n）時間でそのようなすべてのペアを見つけることはできません。一般に、アルゴリズムの実行には、生成される値の数よりも短い時間はかかりません。
お役に立てれば！
于 2012-09-02T07:05:55.253 に答える
5
生成では、できません。配列内のx + y < zすべてxの場合を考えてみます。yセット内のすべてのn(n - 1)/2可能なペアにタッチ（表示など）する必要があります。これは基本的にO（n ^ 2）です。
于 2012-09-02T07:06:24.097 に答える
2
その特性を満たすすべてのペアを出力するように求められた場合、出力にはO（N ^ 2）ペアが含まれる可能性があるため、O（N ^ 2）よりも優れたものはないと思います。
しかし、これはx + y = zにも当てはまり、O（N）解があると主張しているので、何かが足りない可能性があります。
元の質問ではペアの数を尋ねられたのではないかと思います。その場合、O（N log（N））で行うことができます。各要素xについて、y = z --xを見つけ、配列内のyの二分探索を実行します。yの位置は、xの特定の値で形成できるペアの数を示します。配列内のすべての値についてこれを合計すると、答えが得られます。N個の値があり、それぞれのペアがO（log（N））（二分探索）を取る場合の数を見つけるため、全体がO（N log（N））になります。
于 2012-09-02T07:18:56.217 に答える
1
各要素が一意であるという追加の制約を追加すると、O（N）でそれらを見つけることができます。
すべてのx+y == zペアを見つけた後、その条件を満たすすべてのxとyについて、そのペアよりも低いインデックスにあるすべてのxまたはy（1つを選択）がx +y<zを満たすことがわかります。調子。
実際にこれらを選択して出力するにはO（n ^ 2）が必要ですが、ある意味で、x + y == zのペアは、入力とともに、回答の圧縮形式です。
（各要素が一意であるフォームへの入力を、発生回数のカウンターとともに前処理できます。これにはO（N）時間がかかります。このソリューションをソートされていない配列に一般化して、時間をO（nlogn）に増やすことができます。 。）
解のサイズに線形に比例する時間の下でペアを見つけると言うことの正当化：質問が「0と与えられた入力Kの間にある整数は何ですか？」であると仮定します。
于 2012-09-02T07:13:18.200 に答える
1
ソートされた整数配列であるため、二分探索アルゴリズムを使用できます。したがって、最良の場合はO(N)、、最悪O(N*logN)の場合は、平均の場合もO(N*logN)です。
于 2012-09-02T07:21:00.203 に答える
0
配列を並べ替えることができ、z未満のすべての要素に対して、binary-search --total O（NlogN）を使用します。
合計実行時間：O（| P | + NlogN）、ここでPは結果のペアです。
于 2012-09-02T08:30:12.320 に答える
0
この質問に対するO（nlogn）ソリューションが実際に存在します。（許可されているかどうかを最初に確認した後）私が行うことは、アルゴリズム/関数の出力形式を定義することです。
私はそれを一連の要素（S、T）として定義します。S-配列内の要素の位置（またはその値）。T-サブ配列[0、T]の位置。したがって、たとえば、T = 3の場合、要素Sが要素0、1、2、および3と組み合わされて目的の条件を満たすことを意味します。
この結果の合計は、O（nlogn）実行時間とO（n）メモリです。
于 2016-03-17T10:51:38.903 に答える