ソート結果配列

Question

私はこの質問をAdobeのインタビューで受けました：

私たちは、昇順でソートされた整数配列を持っています。我々はまた、3つの整数A,BおよびCを持っています。配列内の各要素xに対してA*x*x + B*x + Cを適用し、対応するソート済み配列を返す必要があります。

私は与えられた例：

Input array = -1 0 1 2 3 4 
A = -1, B = 2, C = -1` 

結果-4 -1 0 -1 -4 -9
=各要素に式を適用したので、期待される結果は= -9 -4 -4 -1 -1 0（ソート）

私の最善の解決策は、以下の式を適用し、それをソートしましたその結果、溶液が得られた。私はそれをうまくできませんでした。

改善の指針は参考になります。

Answer 1

O(n)でこれを行うことができます。あなたはx_minに最も近い整数を見つけるまで

2 * A * x + B = 0 

がよう

x_min = -B/2 * A. 

はその後、配列を歩くときに発生する多項式の最小値を検索します。これはO(n)です。ここから、|x_min - left|が|x_min - right|より小さいか大きいかに応じて、この要素の左または右から順に選択します。結果の順序でこれらの点で多項式を評価する値を返します。これはO(n)です。

これは、Aが肯定的であることを前提としています。同様に負の場合にはAを処理できます。

例：ここ

input array = -1 0 1 2 3 4 A = -1, B = 2, C = -1 

、最大値はx_max = -2/2 * -1 = 1で起こります。入力配列から、最も近い値は1で、3番目の要素です。次に、距離が1に基づいて、次の順序で要素を順番に選択します。 Aがマイナスであるため、

1, 0, 2, -1, 3, 4 

はその後、我々は逆の順序で

4, 3, -1, 2, 0, 1 

をこれらを実行し、それらに

完了

-9, -4, -4, -1, -1, 0 

を多項式を評価する必要があります。

私たちは、パラボラの特別なプロパティを利用しています。すなわち、xがx_extreme未満であり、Aが正である場合、そのようなxに多項式を適用することは、xの減少関数である。 xがx_extremeおよびA陽性より大きい場合、そのようなxに多項式を適用することは、xの増加関数である。（Aが負の場合は同様の推論が適用されます）。したがって、x_extremeより小さいxとx_extremeより大きいxの2つの部分にアレイを分割します。次に、これら2つの部分に多項式を適用して、2つの配列をソートします。これらの並べ替えられた配列にソートされたマージを適用します。上記の説明は効果的にマージソートであることに注意してください。

Answer 2

与えられた式はparabolicです。したがって、ソートされた配列に適用すると、サブ配列が左右にソートされた状態で最大値/最小値を持つ配列になります。

あなたのケースでは最大0であり、その左[-4 -1]にサブ配列が昇順にソートされ、その右[-1 -4 -9]サブ配列を降順でソートされます。

あなたがする必要があるのはこれらの並べ替えられた配列を時間的に直線的にマージすることだけです。

ので、アルゴリズムは次のとおりです。

1. は
検索最大/最小サブアレイ

Answer 3

をマージ

各要素に式を適用するあなたが次の適用の結果を認識することができますデータはほぼソートされています（上記の答えに記載されているように、または次数nの多項式の導関数が次数n-1で連続し、最大でn個のゼロを持つことを認識することによって）。

ソートルーチンがほとんどソートされたデータ（これを念頭に置いているmergesortなど）を使って賢明なやり方をしていれば、そのデータをスローしてリニアなパフォーマンスを期待できます。ウェブを検索すると、http://svn.python.org/projects/python/trunk/Objects/listsort.txtを指すWhich sort algorithm works best on mostly sorted data? が見つかりました。

Answer 4

解決策はO(N)であり、微積分を実行する必要はありませんが、曲線の形状を理解するのに役立ちます。

上記の答えは、最も直感的なことを行い、方程式を解いて最小値または最大値を見つけてリストを分割します。

一次導関数を計算する際に利点がありますが、実際に行う必要はなく、現時点で最大点または最小点を見つける必要はありません。

一方向に移動してからもう一方の方向に戻ることができますが、方向は何度も変わることはありません。

私たちはそれぞれの端から始めて、真ん中のどこかでマージするまで両側から反復します。他に何かをする前に、最後の2つの要素を比較するだけで、それぞれの方向を確認する必要があります。そこで、一方の端が上に移動し、もう一方の端が下に移動しているかどうかを確認します。

我々はN要素を持っている場合我々はそうf(X[0])とf(X[N-1])とf(X[1])とf(X[N-2])を計算し、データX[0]とX[N-1]を持っているとしましょう。 f(X[0]) < f(X[1])とf(X[N-1]) > f(X[N-2])の場合、実際にはすべてのデータは最大値/最小値の片側であるため、すでにソートされています。比較が他の方向にある場合も同じです。（一方向は逆にする必要があります）。

それ以外の場合は、両端のマージを実行してください。したがって、f(X[0])とf(X[N-1])は、サブレンジの最大値または最小値です（これまでの比較からわかります）。そして、どちらか適切な方向からマージリストを作成します。あなたのデータに適用

：

-1 0 1 2 3 4 
A = -1, B = 2, C = -1` 

f = [ -4, -1, 0, -1, -4, -9 ] 

-4 < -1と-9 < -4ので、我々はポイントを横断行い、私たちは各端で最小値を持っています。

-9 is lower than -4 
-4 and -4 are equal so push both 
-1 and -1 are equal so push both 
0 remains. 

our sequence is [-9, -4, -4, -1, -1, 0 ]