前往
大廳
主題

LeetCode - 1200. Minimum Absolute Difference 解題心得

Not In My Back Yard | 2021-04-04 00:00:21 | 巴幣 0 | 人氣 182

題目連結:


題目意譯:
給定一相異整數陣列 arr,找到全部的元素對,其有著任兩個元素對當中最小的絕對差值。

回傳一個列表其以升序(對於元素對們來說)排序元素對們,每對元素 [a, b] 遵從
a 、 b 出現於 arr 中
a < b
b - a 等於於 arr 中任兩個元素的最小可能絕對差值。

限制:
2 ≦ arr.length ≦ 10 ^ 5
-10 ^ 6 ≦ arr[i] ≦ 10 ^ 6



範例測資:
範例 1:
輸入: arr = [4,2,1,3]
輸出: [[1,2],[2,3],[3,4]]
解釋: 最小絕對差值為 1。列舉出所有對,其差值等於 1 並按照升序排列。

範例 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]]


解題思維:
因為我們要求的是最小差值的那些元素對,因此最有潛力的是排序後的每一個相鄰數對。更正確地說,那些最小差值之數對中每對的的必定是排序後彼此會相鄰的數字(不然如果不相鄰,則可以改選相鄰的而產生差值更小的結果)。

因此先將 arr 內的數字由小排到大,接著從小的數字開始掃到大的數字。對於每個數字與其後一個數字形成一個配對,這樣便形成升序的數對,而且所有數對彼此之間也是升序。

接著對於每個數對,判斷該對差值是否有等於當前最小(用一個變數暫存當前找到的最小差值,一開始該變數值要設定為一個很大的值(在本題至少要到 10 ^ 6 - (-10 ^ 6) = 2 × 10 ^ 6),才不會漏掉可能的情況)。如果是,則將該數對加入結果陣列裡;如果是小過當前最小,則將結果陣列清空並且將當前最小更新成該數對之差值。

經過以上步驟之後,結果陣列的內容即是所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

追蹤 創作集

作者相關創作

更多創作