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-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。