LeetCode.1200-最小绝对值差(Minimum Absolute Difference)

来源：cnblogs　　作者：程序员小川　　时间：2019/10/8 9:09:49　　对本文有异议

这是小川的第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;
}