给你个整数数组 arr，其中每个元素都 不相同 。
请你找到所有具有最小绝对差的元素对，并且按升序的顺序返回。
每对元素对 [a,b] 如下：
a , b 均为数组 arr 中的元素a < bb - a 等于 arr 中任意两个元素的最小绝对差
示例 1：
**输入：** arr = [4,2,1,3]
**输出：** [[1,2],[2,3],[3,4]]
示例 2：
**输入：** arr = [1,3,6,10,15]
**输出：** [[1,3]]
示例 3：
**输入：** arr = [3,8,-10,23,19,-4,-14,27]
**输出：** [[-14,-10],[19,23],[23,27]]
提示：
2 <= arr.length <= 10^5-10^6 <= arr[i] <= 10^6
方法一：排序 + 一次遍历
思路与算法
首先我们对数组 arr 进行升序排序。这样一来，拥有「最小绝对差」的元素对只能由有序数组中相邻的两个元素构成。
随后我们对数组 arr 进行一次遍历。当遍历到 arr}[i] 和 arr}[i+1] 时，它们的差为 \delta = \textit{arr}[i+1] - \textit{arr}[i]。我们使用一个变量 best 存储当前遇到的最小差，以及一个数组 ans 存储答案：
代码
[sol1-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
int n = arr.size();
sort(arr.begin(), arr.end());
int best = INT_MAX;
vector<vector<int>> ans;
for (int i = 0; i < n - 1; ++i) {
if (int delta = arr[i + 1] - arr[i]; delta < best) {
best = delta;
ans = { {arr[i], arr[i + 1]} };
}
else if (delta == best) {
ans.emplace_back(initializer_list<int>{arr[i], arr[i + 1]});
}
}
return ans;
}
};
|
[sol1-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public List<List<Integer>> minimumAbsDifference(int[] arr) {
int n = arr.length;
Arrays.sort(arr);
int best = Integer.MAX_VALUE;
List<List<Integer>> ans = new ArrayList<List<Integer>>();
for (int i = 0; i < n - 1; ++i) {
int delta = arr[i + 1] - arr[i];
if (delta < best) {
best = delta;
ans.clear();
List<Integer> pair = new ArrayList<Integer>();
pair.add(arr[i]);
pair.add(arr[i + 1]);
ans.add(pair);
} else if (delta == best) {
List<Integer> pair = new ArrayList<Integer>();
pair.add(arr[i]);
pair.add(arr[i + 1]);
ans.add(pair);
}
}
return ans;
}
}
|
[sol1-C#]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| public class Solution {
public IList<IList<int>> MinimumAbsDifference(int[] arr) {
int n = arr.Length;
Array.Sort(arr);
int best = int.MaxValue;
IList<IList<int>> ans = new List<IList<int>>();
for (int i = 0; i < n - 1; ++i) {
int delta = arr[i + 1] - arr[i];
if (delta < best) {
best = delta;
ans.Clear();
IList<int> pair = new List<int>();
pair.Add(arr[i]);
pair.Add(arr[i + 1]);
ans.Add(pair);
} else if (delta == best) {
IList<int> pair = new List<int>();
pair.Add(arr[i]);
pair.Add(arr[i + 1]);
ans.Add(pair);
}
}
return ans;
}
}
|
[sol1-Python3]1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution:
def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
n = len(arr)
arr.sort()
best, ans = float('inf'), list()
for i in range(n - 1):
if (delta := arr[i + 1] - arr[i]) < best:
best = delta
ans = [[arr[i], arr[i + 1]]]
elif delta == best:
ans.append([arr[i], arr[i + 1]])
return ans
|
[sol1-C]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| static inline int cmp(const void *pa, const void *pb) {
return *(int *)pa - *(int *)pb;
}
int** minimumAbsDifference(int* arr, int arrSize, int* returnSize, int** returnColumnSizes){
qsort(arr, arrSize, sizeof(int), cmp);
int best = INT_MAX;
int **ans = (int **)malloc(sizeof(int *) * (arrSize - 1));
int pos = 0;
for (int i = 0; i < arrSize - 1; ++i) {
int delta = arr[i + 1] - arr[i];
if (delta < best) {
best = delta;
for (int j = 0; j < pos; j++) {
free(ans[j]);
}
pos = 0;
ans[pos] = (int *)malloc(sizeof(int) * 2);
memcpy(ans[pos], arr + i, sizeof(int) * 2);
pos++;
}
else if (delta == best) {
ans[pos] = (int *)malloc(sizeof(int) * 2);
memcpy(ans[pos], arr + i, sizeof(int) * 2);
pos++;
}
}
*returnSize = pos;
*returnColumnSizes = (int *)malloc(sizeof(int) * pos);
for (int i = 0; i < pos; i++) {
(*returnColumnSizes)[i] = 2;
}
return ans;
}
|
[sol1-JavaScript]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| var minimumAbsDifference = function(arr) {
const n = arr.length;
arr.sort((a, b) => a - b);
let best = Number.MAX_VALUE;
let ans = [];
for (let i = 0; i < n - 1; ++i) {
let delta = arr[i + 1] - arr[i];
if (delta < best) {
best = delta;
ans = [];
const pair = [];
pair.push(arr[i]);
pair.push(arr[i + 1]);
ans.push(pair);
} else if (delta === best) {
const pair = [];
pair.push(arr[i]);
pair.push(arr[i + 1]);
ans.push(pair);
}
}
return ans;
};
|
[sol1-Golang]1
2
3
4
5
6
7
8
9
10
11
12
| func minimumAbsDifference(arr []int) (ans [][]int) {
sort.Ints(arr)
for i, best := 0, math.MaxInt32; i < len(arr)-1; i++ {
if delta := arr[i+1] - arr[i]; delta < best {
best = delta
ans = [][]int{ {arr[i], arr[i+1]} }
} else if delta == best {
ans = append(ans, []int{arr[i], arr[i+1]})
}
}
return
}
|
复杂度分析
