LeetCode 1200 Minimum Absolute Difference

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<sup>5</sup>
* -10<sup>6</sup> <= arr[i] <= 10<sup>6</sup>

题目大意：

数组中求最小差值的所有数值pair，pair中按数值排序

解题思路：

其中一个例子是有序的，就联想到排序，然后遍历求最小插值并记录对应的结果

解题步骤：

N/A

注意事项：

N/A

Python代码：

def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
	arr.sort()
	min_diff, res = float('inf'), []
	for i in range(1, len(arr)):
		if arr[i] - arr[i-1] <= min_diff:
			if arr[i] - arr[i-1] < min_diff:
				res = []
				min_diff = arr[i] - arr[i-1]
			res.append([arr[i-1], arr[i]])
	return res

算法分析：

时间复杂度为O(nlogn)，空间复杂度O(1)