algorithm - O(n)で実行される配列「最大差」アルゴリズム?

Question

N 個の整数の配列が与えられた場合、配列を並べ替え、並べ替えられた配列内で最大の差を持つ 2 つの連続する数値を見つけます。

例 – 入力[1,7,3,2]出力4(ソートされた配列は[1,2,3,7]で、最大差は 7-3=4)。

アルゴリズム A はO(NlogN)時間内に実行されます。

O(N) 時間で実行される、アルゴリズム A と同じ機能のアルゴリズムを見つける必要があります。

Answer 1

配列を X とし、n = length(X) とします。各要素 x をバケット番号 floor((x - min(X)) * (n - 1) / (max(X) - min(X))) に入れます。各バケットの幅は (max(X) - min(X))/(n - 1) であり、隣接する最大の差は少なくともそれだけであるため、問題の数値は異なるバケットになります。あとは、一方がバケット i の最大値で、もう一方がバケット j の最小値であるペアを検討するだけです。ここで、i < j で、(i, j) のすべてのバケット k は空です。これは線形時間です。

本当に床が必要であることの証明: 関数を f(X) とします。f(X) を線形時間で計算できれば、確かに線形時間で決定できるかどうかを決定できます。

0 < f(X) ≤ (最大(X) - 最小(X))/(長さ(X) - 1)、

つまり、X の要素が等間隔であり、すべてが同一ではないかどうか。この述語を P(X) とする。P のサポートには factorial(length(X)) 連結要素があるため、計算の代数モデルの通常の Ω(n log n) 下限が適用されます。

Answer 2

カウントソートを実行してから、結果をスキャンして最大の差を探します。

連続番号の要件があるため、一見すると、どのソリューションでも並べ替えが必要になるように見えます。これは、番号範囲がカウント並べ替えに対して十分に制約されていない限り、せいぜいO（ n log n ）を意味します。しかしそうであれば、O（n）で勝ちます。