給定一個不同整數的陣列arr，找出任意兩個元素的絕對差最小的所有元素對。
按升序回傳對串列（相對于對），每對[a, b]如下
a, b來自arra < bb - a等于 中任意兩個元素的最小絕對差arr。
示例 1：
輸入：arr = [4, 2, 1, 3]
輸出：[[1, 2], [2, 3], [3, 4]]
解釋：最小絕對差為 1。按升序列出差等于 1 的所有對。
解決方案（效率較低）
class Solution:
def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
minimum = abs(max(arr)) - (min(arr))
u = minimum
for r in arr:
for t in arr:
if r - t != 0:
minimum = abs(r - t)
if minimum < u:
u = minimum
else:
minimum = minimum
result = []
for i in arr:
for x in arr:
if x != i and abs(i - x) == u and [x, i] not in result and [i, x] not in result:
h = [i, x]
h.sort()
result.append(h)
result.sort()
return result
uj5u.com熱心網友回復：
很明顯，對串列進行排序會將最接近的元素放在一起。排序通常是一個 O(n log n) 操作。
arr.sort()
找到最小值需要單次通過來比較相鄰元素。幾乎任何你做的方式都是 O(n)。一個非常簡單的實作是
x = iter(arr)
next(x)
min_dist = min(b - a for a, b in zip(arr, x))
一個更簡單的：
min_dist = min(arr[i 1] - arr[i] for i in range(len(arr) - 1))
獲得對現在是檢查用于計算的任何生成器中的任何差異是否min_diff等于min_diff。這顯然也是一個 O(n) 操作。
pairs = [arr[i:i 2] for i in range(len(arr) - 1) if arr[i 1] - arr[i] == min_diff]
由于排序的復雜性占主導地位，整個演算法是 O(n log n)，這可能是最優的，并且肯定比現有的 O(n^2) 實作更好。
正如@luk2302 在評論中所建議的那樣，您可以通過累積當前最小值的對來避免第二次傳遞：
arr.sort()
if len(arr) < 2: return []
pairs = [arr[:2]]
current_minimum = arr[1] - arr[0]
for i in range(2, len(arr)):
z = arr[i - 1:i 1]
if (n := z[1] - z[0]) < current_minimum:
pairs = [z]
current_minimum = n
elif n == current_minimum:
pairs.append(z)
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/387588.html
上一篇：漸近符號的使用