漫畫算法：無序數組排序后的最大相鄰差值

小灰一邊回憶一邊講述起當時面試的情景……

題目：有一個無序整型數組，如何求出這個數組排序后的任意兩個相鄰元素的最大差值？要求時間和空間復雜度盡可能低。（例如：無序數組 2,3,1,4,6，排序后是1,2,3,4,6，最大差值是6-4=2）

解法一：

用一種較快的穩定排序算法（比如歸并算法，時間復雜度N*logN）給原數組排序，然后遍歷排好序的數組，每兩個相鄰元素求差，最終得到最大差值。

該解法的時間復雜度是O（N*logN），在不改變原數組的情況下，空間復雜度是O（N）。

解法二：

1.利用計數排序的思想，先求出原數組的最大值Max與最小值Min的區間長度k（k=Max-Min+1）。

2.創建一個長度為k的新數組Array。

3.遍歷原數組，把原數組每一個元素插入到新數組Array對應的位置，比如元素的值為n，則插入到Array[n-min]當中。此時Array的部分位置為空，部分位置填充了數值。

4.遍歷新數組Array，統計出Array中最大連續出現空值的次數+1，即為相鄰元素最大差值。

例如給定無序數組 { 2, 6, 3, 4, 5, 10, 9 }，處理過程如下圖：

該解法的時間復雜度為O（n+k），空間復雜度同樣是O（n+k）。

解法三：

1.利用桶排序的思想，先求出原數組從最小值Min到最大值Max的單位區間長度d，d=(Max-Min)/n。算出d的作用是為了后續確定各個桶的區間范圍劃分。

2.創建一個長度是N+1的數組Array，數組的每一個元素都是一個List，代表一個桶。

3.遍歷原數組，把原數組每一個元素插入到新數組Array對應的桶當中，進入各個桶的條件是根據不同的數值區間（數值區間如何劃分，看后面的圖就明白了）。由于桶的總數量是N+1，所以至少有一個桶是空的。

4.遍歷新數組Array，計算每一個空桶 右端非空桶中的最小值 ，與空桶 左端非空桶的最大值 的差，數值最大的差即為原數組排序后的相鄰最大差值。

例如給定無序數組 { 0, 6, 3, 16, 7, 10, 9, 11, 20, 18 }，處理過程如下圖：

該解法的時間復雜度為O（n），空間復雜度同樣是O（n）。

十分鐘后……

以上就是小灰面試的情況……

 

 

來自：http://blog.jobbole.com/108594/