1200. 最小绝对差

题目描述：

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

---

解题分析及思路：

首先这是一道简单题，简单题就不需要用太复杂的算法进行解答。

首先要关注的一个点是并且按升序的顺序返回，也就是说这一题涉及到排序。

其次，要关注的点是具有最小绝对差的元素，也就是不同元素的比较。

1. 排序：go的基础包里面就包含了数组的排序，直接调用sort.Ints(arr)方法即可实现排序。

2. 比较：涉及到比较就需要考虑两数相加减是否会有值溢出的情况，本文数组的值范围在**-10^6 <= arr[i] <= 10^6**，及时极限情况下做两个数的加减法，还是不会超过int的最大值或最小值，所以无需考虑值的溢出情况

3. 找出最小绝对差的元素对，那么怎么找到最小绝对差呢？ 什么样的情况最好找到最小绝对差呢？那就是这个数组是有序的情况下，那么对这个数组进行排序不就好了。然后用后一个减去前一个得到一个差值，比较每一次差值的情况就可以得到，最小绝对差了。

4. 第二部分：按升序的顺序返回，因为前一步已经将数组进行排序，所以直接遍历数组，查看后一个和前一个的差值是否等于最小绝对差，如果等于那么直接放入最后结果里，否则则舍弃该元素组。

代码分析：

1. 排序

sort.Ints(arr)

2. 获得最小绝对差

var min int
for i := 1; i < len(arr); i++ {
    if i == 1 {
        min = arr[i] - arr[i-1]
    } else {
        temp := arr[i] - arr[i-1]
        if temp < min {
            min = temp
        }
    }
}

优化，获得int的最大值int(^uint(0) >> 1)，即可省去下标为1的情况判断。

var min int = int(^uint(0) >> 1)
for i := 1; i < len(arr); i++ {
    temp := arr[i] - arr[i-1]
    if temp < min {
        min = temp
    }
}

3. 获取期望结果

res := make([][]int, 0)
for i := 1; i < len(arr); i++ {
    if arr[i]-arr[i-1] == min {
        res = append(res, []int{arr[i-1], arr[i]})
    }
}

复杂度：

• 时间复杂度：O(nlogn)，排序所需时间
• 空间复杂度：O(logn)，排序所需空间

执行结果：

• 执行用时： 64 ms , 在所有 Go 提交中击败了 82.19% 的用户
• 内存消耗： 8.2 MB , 在所有 Go 提交中击败了 50.68% 的用户