在數組中尋找條件極小差異的算法

-2

假設你有一個不同整數的數組：A = [a1，a2，a3，a4，a5 ...] 我需要找到數組的兩個元素，比如A [ i]和A [j]，使得i小於j並且A [j] -A [i]是最小的。在數組中尋找條件極小差異的算法

下面是一個有效的解決方案嗎？

陣列首先排序，並保持每個元素的原始索引（即，軌道：所述元件的原件中的索引（未排序）陣列
經過排序後的數組，並計算任何之間的差異該驗證的初始條件，即更大的元素的原始索引小於更小的元素的原始索引更大兩個連續的元件。
答案將是所有這些不同的最小值。

這裏是這對於前者如何工作？充足的：

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

來源

2013-03-25 user2205925

你的第一句話是不完整的。 – eliot 2013-03-25 01:47:08

謝謝艾略特我現在修好了。任何線索，如果這種方法可能工作？ – user2205925 2013-03-25 02:04:24

如果對輸入進行排序：[ - 1,0,2,10]，則取前兩個元素：-1和0.在前面，未排序的數組-1是AFTER 0，所以初始條件「i is less比j和A [j] -A [i]最小「未被驗證，因爲我比j大。然後你移動到0和2，差別是2.這是我們有效的區別，因爲元素2是未排序數組中的元素1之後的元素。然後你移動到2和10，差異是8.找到的最小差異是2，所以這是答案。你怎麼看？ – user2205925 2013-03-25 02:41:10

這是一個解決方案，它是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-25 02:06:07

這需要O（n^2），我在尋找O（nlog（n）），有什麼想法？ – user2205925 2013-03-25 03:04:13

如果你想找到什麼是積極的最小差異，那麼基本上，你的問題是：

Find two closest elements in an array.

的O（nlogn）的解決方案很簡單：

sort - O（nlogn）
獲取兩個相鄰元素之間的差異並找到最小的一個 - O（n）

所以整體運行時間爲O（nlogn）

你不必在意指數。因爲你什麼是abs(A[i]-A[j])=abs(A[j]-A[i])，沒關係i>j或j>i

來源

2013-03-25 02:45:28 gongzhitaao

你說的是對的。然而，就這個問題而言，我只是在兩個元素之間尋找最小差值A [j] -A [i]，以驗證初始條件j> i（在初始數組中）。我的算法看起來好嗎？ – user2205925 2013-03-25 03:15:57

@ user2205925不是。因爲你跳過一些潛在的答案，因爲「i> j」或「j> i」，這實際上並不重要。例如''[1,0,3,5]'' – gongzhitaao 2013-03-25 03:18:44

我的意思是說，如果我不是在尋找絕對最小差異，而是驗證條件i user2205925 2013-03-25 03:24:20

在數組中尋找條件極小差異的算法

回答

相關問題