-2

異なる整数の配列があるとします: A=[a1,a2,a3,a4,a5...] 配列の 2 つの要素を見つける必要があります。たとえば、A[i] と A[j] で、i はそれより小さくなります。 j および A[j]-A[i] よりも最小です。

以下は有効な解決策ですか？

  1. 最初に配列をソートし、各要素の元のインデックス (つまり、元の (ソートされていない) 配列内の要素のインデックス) を追跡します。
  2. 並べ替えられた配列を調べて、2 つの連続する要素間の差を計算します。これにより、大きい要素の元のインデックスが小さい要素の元のインデックスよりも大きいという初期条件が検証されます。
  3. 答えは、これらすべての差の最小値になります。

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

A=[0,-5,10,1]  (in this case the result should be 1 coming from the difference between      A[3] and A[0])
sort A : newA=[-5,0,1,10]
since OriginalIndex(-5)>OriginalIndex(0), do not compute the difference
since OriginalIndex(1)>OriginalIndex(0),we compute the difference =1
since OriginalIndex(10)>OriginalIndex(1), we compute the difference =9
The result is the minimal difference, which is 1
4

2 に答える 2

0

見つけたいのが正の最小差である場合、基本的に、問題は次のとおりです。

Find two closest elements in an array.

O(nlogn) ソリューションは簡単です。

  1. ソート -- O(nlogn)
  2. 隣接する 2 つの要素の差を取得し、最小のものを見つけます -- O(n)

したがって、全体の実行時間は O(nlogn) です

インデックスを気にする必要はありません。あなたが何であるか、abs(A[i]-A[j])=abs(A[j]-A[i])それは問題ではないので、i>jj>i

于 2013-03-25T02:45:28.690 に答える
0

ここに 1 つの解決策があります。時間は O(n^2) ですが、空間は O(1) です。擬似コード:

for i = 0; i < array.length; i++
    for j = i + 1; j < array.length; j++
        if a[j] - a[i] < min
            min = a[j] - a[i]
return min
于 2013-03-25T02:06:07.340 に答える