1200. 最小绝对差

🟢   🔖  数组 排序  🔗 力扣 LeetCode

题目

Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference of any two elements.

Return a list of pairs in ascending order(with respect to pairs), each pair [a, b] follows

• a, b are from arr
• a < b
• b - a equals to the minimum absolute difference of any two elements in arr

Example 1:

Input: arr = [4,2,1,3]

Output: [[1,2],[2,3],[3,4]]

Explanation: The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.

Example 2:

Input: arr = [1,3,6,10,15]

Output: [[1,3]]

Example 3:

Input: arr = [3,8,-10,23,19,-4,-14,27]

Output: [[-14,-10],[19,23],[23,27]]

Constraints:

• 2 <= arr.length <= 10^5
• -10^6 <= arr[i] <= 10^6

题目大意

给你个整数数组 arr，其中每个元素都 不相同 。

请你找到所有具有最小绝对差的元素对，并且按升序的顺序返回。

每对元素对 [a,b] 如下：

• a , b 均为数组 arr 中的元素
• a < b
• b - a 等于 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. 排序数组：
   将数组 arr 按升序排序。这样可以保证相邻的两个数之间的差值是局部最小的。

2. 遍历寻找最小差值：
   遍历排序后的数组，计算每一对相邻元素的差值。

   • 如果当前差值小于之前的最小差值，更新最小差值，并清空结果数组 res，将当前数对加入结果。
   • 如果当前差值等于最小差值，将当前数对直接加入结果数组。

3. 返回结果：
   返回所有最小差值的数对组成的数组。

复杂度分析

• 时间复杂度：O(n log n)，其中 n 是数组的长度，数组排序的时间开销。
• 空间复杂度：O(n)，结果数组所需的空间。

代码

/**
 * @param {number[]} arr
 * @return {number[][]}
 */
var minimumAbsDifference = function (arr) {
	// 将数组按升序排序
	arr.sort((a, b) => a - b);

	// 初始化结果数组和最小差值
	let res = [];
	let minDistinct = Infinity;

	// 遍历排序后的数组，寻找最小绝对差
	for (let i = 1; i < arr.length; i++) {
		const dist = Math.abs(arr[i] - arr[i - 1]); // 当前差值

		if (dist < minDistinct) {
			// 如果发现更小的差值，更新最小差值并清空结果数组
			res.length = 0;
			minDistinct = dist;
			res.push([arr[i - 1], arr[i]]);
		} else if (dist === minDistinct) {
			// 如果差值等于最小差值，将当前数对加入结果
			res.push([arr[i - 1], arr[i]]);
		}
	}

	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
2144	打折购买糖果的最小开销	[✓]	贪心 数组 排序	🟢	🀄️ 🔗
2616	最小化数对的最大差值		贪心 数组 二分查找	🟠	🀄️ 🔗