LEETCODE 1200. Minimum Absolute Difference 解题思路分析

题目大意：

最小绝对差

给你个整数数组 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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1200

解题思路分析：

1. 先将数组升序排序
2. 从下标1开始循环，计算arr[i]-arr[i-1]的差值，如果此差值为最小差值，就将arr[i]和arr[i-1]存入返回结果。
3. 如果发现了更小的差值，先把返回结果清空，并将当前两数存入反回结果中。

完整代码：

public List<List<Integer>> minimumAbsDifference(int[] arr) {
    Arrays.sort(arr); // 数组排序
    List<List<Integer>> res = new ArrayList<>(); // 返回结果
    int minDiff=Integer.MAX_VALUE; // 记录最小差值
    for(int i=1;i<arr.length;i++){ // 循环数组
        int diff= arr[i]-arr[i-1]; // 计算当前两数差值
        if(diff<=minDiff){ // 如果小于等于最小差值
            if(diff<minDiff){ // 如果小于最小差值
                minDiff = diff; // 更新最小差值
                res.clear(); // 清空返回结果
            }
            // 将当前两数加入返回结果。
            List<Integer> list = new ArrayList<>();
            list.add(arr[i-1]);
            list.add(arr[i]);
            res.add(list);
        }
    }
    return res;
}

本题解法运行时间为20ms.

Runtime: 20 ms, faster than 96.14% of Java online submissions forMinimum Absolute Difference.

Memory Usage: 51.3 MB, less than 100.00% of Java online submissions for Minimum Absolute Difference.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1200-minimum-absolute-difference-解题思路分析/