題目
給你個整數數組 arr,其中每個元素都 不相同。
請你找到所有具有最小絕對差的元素對,并且按升序的順序傳回。
每對元素對 [a,b] 如下:
- a , b 均為數組 arr 中的元素
- a < b
- b - a 等于 arr 中任意兩個元素的最小絕對差
示例1:
輸入:arr = [4,2,1,3]
輸出:[[1,2],[2,3],[3,4]]
示例2:
輸入:arr = [1,3,6,10,15]
輸出:[[1,3]]
輸入:arr = [3,8,-10,23,19,-4,-14,27]
輸出:[[-14,-10],[19,23],[23,27]]
解題思路
- 與最小絕對差相等,加入答案。
- 比最小絕對差小,清空答案并更新最小絕對差,然後加入新答案。
- 比最小絕對差大,直接跳過
代碼實作
public List<List<Integer>> minimumAbsDifference(int[] arr) {
//排序
Arrays.sort(arr);
int min = Integer.MAX_VALUE;
List<List<Integer>> ans = new ArrayList<>();
for (int i = 1; i < arr.length; i++) {
if (arr[i] - arr[i - 1] < min) {
//比最小絕對差小
ans.clear();
min = arr[i] - arr[i - 1];
} else if (arr[i] - arr[i - 1] > min) {
//比最小絕對差大
continue;
}
//添加答案
List<Integer> list = new ArrayList<>();
list.add(arr[i - 1]);
list.add(arr[i]);
ans.add(list);
}
return ans;
}
複雜度分析
- 時間複雜度:O(nlogn)
- 空間複雜度:O(logn)