題目
給定一個無序數組, 返回其排序後相鄰兩數差值的最大值.
例如數組元素為 [2, 5, 1, 0], 排序後為[0, 1, 2, 5], 相鄰兩數差值分別為 [1, 1, 3], 那麼就返回3
數組中元素為整數, 範圍不定.
要求時間複雜度為 O(n)
思路分析
看過題目後, 首先想到的是先排序, 然後分別計算差值, 返回差值中的最大值即可.
但是又要求時間複雜度為O(n), 比較排序算法都比 O(n)要大的多, 那麼剩下桶排序了, 計數排序可以麼? 數字範圍不定, 計數排序也不行, 但是能達到O(n)的時間複雜度, 也不知道其他的算法啊, 傷腦筋, 那麼怎麼辦呢?
既然計數排序因為數據範圍的原因, 不能實現, 那我們能不能根據數據的個數來構建桶呢?
根據數據個數構建桶的思路:
如果有9個數據, 那麼就構建9個桶, 將數據範圍切分為9等分, 這樣就可以按照桶排序將9個數據放到9個桶中, 相鄰數的差值就可以求了. 但是, 這樣就所有數據的差值都要求, 還要對桶中的數據進行排序, 如此就令時間複雜度又高了. 如何解決這個問題呢?
9個數據, 我們可以構建10個桶啊, 最小的桶和最大的桶中是一定有值的(因為我們是根據數據確定範圍的), 那麼中間可以保證有一個空桶, 而數據的最大差值就一定是在桶間求得的, 因為空桶兩側的差值最少是桶的範圍, 就可以將桶內排除了, 這樣桶內只需要保留此範圍的最大值於最小值即可, 因為排序後桶間相鄰的數就是最大值與最小值.
這樣在求差值時, 只要將兩桶間的相鄰數據進行計算, 然後將計算得出的值中查找最大差值即可, 為什麼不只計算空桶兩側的差值呢?
舉個例子, 如下圖:
好, 基本思路已經明確了, 下面是我簡單的代碼實現:
簡單的桶結構:
算法主體:
計算數據應放入幾號桶的式子:
結束!!!
閱讀更多 牛牛的編程之路 的文章
