简单

问题描述

给你个整数数组 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 <= 105
• -106 <= arr[i] <= 106

排序

对数组内元素从小到大排序，拥有「最小绝对差」的元素对只能由有序数组中相邻的两个元素构成，一一比较相邻两个元素的差值并记录历史最小差值，若当前两元素差值比历史差值还小，则将答案数组更新为当前两个元素并更新历史差值，若与历史差值相等，则将当前两个元素加入答案数组中。

/**
 * @param {number[]} arr
 * @return {number[][]}
 */
var minimumAbsDifference = function (arr) {
  arr.sort((a, b) => a - b)
  let ans = []
  let min = Infinity
  for (let i = 0; i < arr.length - 1; i++) {
    const diff = arr[i + 1] - arr[i]
    if (diff < min) {
      min = diff
      ans = [[arr[i], arr[i + 1]]]
    } else if (diff === min) {
      ans.push([arr[i], arr[i + 1]])
    }
  }
  return ans
}

• 时间复杂度：$O(n\;log\;n)$
• 空间复杂度：$O(log\;n)$