題目
- 164. 最大間距
- 難度：困難
題目描述
給定一個無序的數組，找出數組在排序之後，相鄰元素之間最大的內插補點。
如果數組元素個數小于 2，則傳回 0。
示例 1:
輸入: [3,6,9,1]
輸出: 3
解釋: 排序後的數組是 [1,3,6,9], 其中相鄰元素 (3,6) 和 (6,9) 之間都存在最大內插補點 3。
示例 2:
輸入: [10]
輸出: 0
解釋: 數組元素個數小于 2，是以傳回 0。
說明:
- 你可以假設數組中所有元素都是非負整數，且數值在 32 位有符号整數範圍内。
- 請嘗試線上性時間複雜度和空間複雜度的條件下解決此問題。
題解
分析
要解決該題目，我們通過觀察示例，優先考慮其邊界情況，即當數組長度為 1 或為空時，此時最大間距應該為 0；
其次，由于一開始給定的數組是無序的，而最終需要在排序後的數組找出結果，是以我們先對數組進行排序操作，調用
sort()
方法即可，其内部是一個歸并排序，是以時間複雜度是
O(nlogn)
；
排序後，我們通過周遊數組，分别計算相鄰元素之間的內插補點，然後進行比較之後取出間距最大值傳回即可，此時主要進行周遊操作，時間複雜度為
O(n)
；
是以最終時間複雜度為
O(nlogn)
；
代碼
public int maximumGap(int[] nums) {
if(nums.length <= 1){
return 0;
}
Arrays.sort(nums);
int res = 0;
for(int i = 0; i < nums.length - 1; i++){
int tmp = nums[i + 1] - nums[i];
if(tmp > res){
res = tmp;
}
}
return res;
} 複制