0

配列 A = [a1, a2, a3, a4, a5...] があり、配列の 2 つの要素、たとえば A[i] と A[j] を見つけて、i が j より小さく、A [j]-A[i] は最小で正です。

ランタイムは O(nlog(n)) でなければなりません。

このコードは仕事をしますか：

  1. 最初に配列をソートし、各要素の元のインデックス (つまり、元の (ソートされていない) 配列内の要素のインデックス) を追跡します。

  2. 並べ替えられた配列を調べて、2 つの連続する要素間の差を計算します。これにより、大きい要素の元のインデックスが小さい要素の元のインデックスよりも大きいという初期条件が検証されます。

  3. 答えは、これらすべての差の最小値になります。

これが例でどのように機能するかを次に示します。

A = [0, -5, 10, 1]

A[3]この場合、結果はとの差から 1 になるはずA[0]です。

  • 並べ替え A : newA=[-5,0,1,10]

  • OriginalIndex(-5)>OriginalIndex(0) であるため、差を計算しない

  • OriginalIndex(1)>OriginalIndex(0) であるため、差 = 1 を計算します。

  • OriginalIndex(10)>OriginalIndex(1) であるため、差 = 9 を計算します。

結果は、最小の差である 1 です。

4

2 に答える 2

2

他の投稿で行われた主張に反して、アルゴリズムの実行時間に関して問題はありません。たとえば、ヒープソートを使用するO(n log n)と、質問の上限として指定されたとおりに配列をソートできます。ソートされた配列に沿って 1 回追加O (n)で実行しても、これ以上害を及ぼすことはないため、引き続き runtime を使用しますO (n log n)。

残念ながら、正しい結果が得られないため、あなたの答えはまだ正しくないようです。

与えられた例を詳しく見てみると、それを自分で確認できるはずです。あなたの例で与えられた配列は次のとおりです。A=[0,-5,10,1]

0 から数えてインデックスを選択i=2し、としてj=3与えられた要件を満たします。選択した値との差を計算すると、アルゴリズムのアプリケーション例で計算された最小値よりも確実に小さくなります。i < j2 < 3A[j] - A[i]A[3] - A[2]1 - 10 = -91

于 2013-03-25T03:32:47.267 に答える
1

要素間の距離を最小限に抑えているため、並べ替えられたリスト内で隣り合っている必要があります (そうでない場合、その間の要素はそれらの 1 つまでの距離が短くなります -> 矛盾)。あなたのアルゴリズムは指定どおりに O(nlogn) で実行されるので、私には問題ないようです。

于 2013-03-25T03:05:17.633 に答える