在O（n）中運行的數組「最大差異」算法？

給定一個N個整數的數組，對數組進行排序，然後在排序後的數組中找到兩個連續的數字，其中最大的差值。示例 - 對輸入[1,7,3,2]輸出4（排序數組爲[1,2,3,7]，最大差值爲7-3 = 4）。算法A在O（NlogN）時間內運行。在O（n）中運行的數組「最大差異」算法？

我需要找到一個功能與算法A相同的算法，它運行在O（N）時間。

UPDATE：

解決方案： http://cgm.cs.mcgill.ca/~godfried/teaching/dm-reading-assignments/Maximum-Gap-Problem.pdf

來源

2012-04-21 daremy

到目前爲止，您探索了哪些路徑？ – 2012-04-21 20:59:46

你只需要返回最大差異，對吧？你不必返回排序的數組呢？ – 2012-04-21 21:02:17

計數和基數排序可能會給你O（n）。從那裏你可以很容易地使用O（n）算法找出最大差異。 O（n）+ O（n）= O（n）。 – 2012-04-21 21:06:41

讓數組爲X並讓n = length（X）。將每個元素x放入桶號樓層（（x - min（X））*（n - 1）/（max（X） - min（X）））。每個桶的寬度是（max（X） - min（X））/（n - 1），最大鄰接差異至少是那麼多，因此所討論的數量會在不同的桶中出現。現在我們所要做的就是考慮這樣的對，其中一個是桶i中的最大值，另一個是桶j中的最小值，其中我（i，j）中的所有桶k都是空的。這是線性時間。

證明我們確實需要floor：讓函數爲f（X）。如果我們能夠以線性時間計算f（X），那麼當然我們可以在線性時間內確定是否可以在線性時間內確定是否在線性時間內確定是否可以在線性時間內確定是否可以在線性時間內確定f（X）是否爲0（最大（X） - 最小（X））/（長度（X） 1），

即，X的元素是否均勻間隔且不是全部相同。讓這個謂詞爲P（X）。 P的支持具有階乘（長度（X））連通分量，所以計算的代數模型的通常的Ω（nlogn）下限適用。

來源

2012-04-21 21:51:19 zxc

感謝您的解釋，我想了解最後的聲明 _讓這個謂詞是P（X）。 P的支持具有階乘（長度（X））連通分量，所以計算的代數模型的通常Ω（n log n）下限適用。除非我建立不變量的規則，我覺得我很難與問題糾纏在一起這可能會幫助我更好地解釋這個問題，儘管我直觀地理解了它的工作方式 – Sid 2016-11-21 21:05:20

執行一個Counting Sort然後掃描最大差異的結果。

由於連續數要求的，乍一看好像任何解決方案都需要排序，這意味着最好O（ñ日誌ñ），除非你的號碼範圍足夠約束的計數排序。但是，如果是這樣，你就贏得了O（n）。

來源

2012-04-21 21:09:36 DigitalRoss

正如OJ指出的那樣，基數排序也應該起作用。我一直喜歡基數排序，但不幸的是，大多數問題似乎涉及到字符數據... – DigitalRoss 2012-04-21 21:16:19

是的，在正常的現實生活中，它可以工作，但在這個任務中，整數範圍不受限制。我想這可以在沒有排序的情況下完成。 – daremy 2012-04-21 21:18:23

它總是O（n），檢查我的解決方案。 – 2015-05-16 06:57:19

查找最小和最大
通過將所有值小於k到左和大於k向右從陣列
排序選擇一個隨機數k的算法。
你知道兩個組的最小值和最大值，計算左邊組的寬度，假設這些值在海峽線上。對正確的團隊也一樣。
轉到第2組，得到更大的gape，你知道該組的最小和最大。直到所選組的數值不超過4個爲止。
你現在只有4個元素的組，並進行排序並找到解決方案。

下面是這種算法是如何工作的一個例子：

輸入：9 5 3 4 12 9 31 17
送隨機數：K = 9
排序更小和更大的k的值
5 3 4 9 9 12 31 17，k是在指數3
左組張口=（9 + 3）/（4 - 1）= 4
鑽機HT組張口=（31 + 9）/（5 - 1）= 10
我們挑選合適的組9 9 12 31 17
送隨機數：K = 12
排序的更小和更大的值ķ
9 9 12 31 17，k是在索引2
左組張口=（12 + 9）/（31）= 11.5
右組張口=（31 + 12）/（3 - 1）= 21.5
12 31 17中的最大增益是31 - 17 = 14

我的算法與Selection Algorithm非常相似，用於在線性時間內找到排序算法的k指數值。

來源

2015-05-16 06:55:11

在O（n）中運行的數組「最大差異」算法？

回答

相關問題