如何在不改變順序的情況下查找數組中兩個數字之間的最小差異，使它們的差異爲正數？

根據年份我給了噸收穫。
像{3,6,12,1,20,25}。

找到有序年份收穫之間收穫的最小差異。
對於給定示例差異是2，因爲3 - 1 = 2。保留順序和結果爲正數
排序不適用，因爲數字已根據年份排序。

一種方法是找到所有正面差異，選擇最小的一個。
但它需要O（n^2）。

有沒有更快的方法來做到這一點？
主要任務是找到數組中元素之間的最小差異，而不改變元素的順序，使它們的差異爲正。如何在不改變順序的情況下查找數組中兩個數字之間的最小差異，使它們的差異爲正數？

來源

2016-11-19 Baimyrza Shamyr

我想你一定是誤解了「連續」這個詞。要麼你的描述不正確，要麼你的理解是錯誤的。 – ruakh

3和1在您的示例中不連續。問題是一致的。 – kraskevich

我會改進。 –

根據我的問題的理解，我們需要計算min(a[i] - a[j])所有有效i中和j這樣i < j和a[i] > a[j]。

可以在陣列上遍歷從左至右，並保持在能夠有效地支持insert和upper_bound操作的數據結構中的所有元件（例如，在C的std::set ++或Java中的TreeSet）。

的僞代碼（C++等）可以是這樣的：

s = empty set 
res = INF 
for elem in array: // from left to right 
    if s.upper_bound(elem) != s.end(): // checks if there is a larger element 
      res = min(res, *s.upper_bound(elem) - elem) 
    s.insert(elem)

插入件和UPPER_BOUND操作花費時間O(log N)，所以總的時間複雜度是O(N log N)。

來源

2016-11-19 19:21:27 kraskevich

它的工作！我不知道那個treeSet保持元素排序。 –

你能解釋一下這個算法的工作原理嗎？ – skrtbhtngr

@skrtbhtngr我認爲這是不言自明的。我們只是遍歷從左到右的所有元素，使用標準庫數據結構找到我們已經看過的最小元素大於給定元素的元素，並將新元素添加到此結構中。 – kraskevich

-1

如果您比較每個值與其他每個值，它將是O（n^2）。所以一個可能的答案可能是採取輔助數組中的值，將其排序爲O（n * ln（n）），然後在一次遍歷中找到最小連續差異。我找不出一個O（n）解決方案。（如果輸入數據有一些限制，可能會有一個）。

來源

2016-11-19 19:24:19 crypton3535

如何在不改變順序的情況下查找數組中兩個數字之間的最小差異，使它們的差異爲正數？

回答

相關問題