这是小川的第418次更新，第451篇原创
看题和准备
今天介绍的是LeetCode算法题中Easy级别的第268题（顺位题号是1200）。给定一个由不同的整数组成的数组arr，找到所有对元素，其中任意两个元素的绝对差值都最小。
以升序返回关于配对的列表（相对于配对），每对[a，b]紧随其后：
- a，b来自
arr - a < b
b-a等于arr中任何两个元素的最小绝对差
例如：
输入：arr = [4,2,1,3]
输出：[[1,2],[2,3],[3,4]]
说明：最小绝对差为1。以升序列出所有差等于1的对。
输入：arr = [1,3,6,10,15]
输出：[[1,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中的最小绝对差值，通过排序来完成，借助Arrays的sort方法实现，因为绝对值差最小的两个数肯定是相邻越近越小。第二，再次遍历arr数组，将绝对值差等于最小绝对值差的两个元素添加到结果list中去。
public List<List<Integer>> minimumAbsDifference(int[] arr) {
Arrays.sort(arr);
int min = Integer.MAX_VALUE, len = arr.length;
for (int i=1; i<len; i++) {
min = Math.min(min, arr[i]-arr[i-1]);
}
List<List<Integer>> result = new ArrayList<List<Integer>>();
for (int i=1; i<len; i++) {
if (arr[i]-arr[i-1] == min) {
List<Integer> list = new ArrayList<Integer>();
list.add(arr[i-1]);
list.add(arr[i]);
result.add(list);
}
}
return result;
}第二种解法
针对第一种解法，我们还可以简化下，只使用一个循环。在循环里判断最小绝对值差，如果当前两元素的绝对值小于最小绝对值差，则更新最小绝对值差的值，同时将结果list清空，这里清空list有两种办法，一是重新创建对象，二是使用clear方法，推荐第一种重新创建对象的做法，将两元素存入结果list中。
public List<List<Integer>> minimumAbsDifference2(int[] arr) {
Arrays.sort(arr);Arrays.sort(arr);
int min = Integer.MAX_VALUE, len = arr.length;
List<List<Integer>> result = new ArrayList<List<Integer>>();
for (int i=1; i<len; i++) {
if (arr[i] - arr[i-1] <= min) {
if (arr[i] - arr[i-1] < min) {
min = arr[i] - arr[i-1];
result = new ArrayList<List<Integer>>();
}
result.add(Arrays.asList(arr[i-1], arr[i]));
}
}
return result;
}小结
算法专题目前已更新LeetCode算法题文章274+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、在看就是对我最大的回报和支持！
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
