comments | difficulty | edit_url | rating | source | tags | ||
---|---|---|---|---|---|---|---|
true |
Easy |
1198 |
Weekly Contest 155 Q1 |
|
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 fromarr
a < b
b - a
equals to the minimum absolute difference of any two elements inarr
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 <= 105
-106 <= arr[i] <= 106
According to the problem description, we need to find the minimum absolute difference between any two elements in the array
Finally, we traverse the adjacent elements again to find all pairs of elements where the minimum absolute difference equals
The time complexity is
class Solution:
def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
arr.sort()
mi = min(b - a for a, b in pairwise(arr))
return [[a, b] for a, b in pairwise(arr) if b - a == mi]
class Solution {
public List<List<Integer>> minimumAbsDifference(int[] arr) {
Arrays.sort(arr);
int n = arr.length;
int mi = 1 << 30;
for (int i = 0; i < n - 1; ++i) {
mi = Math.min(mi, arr[i + 1] - arr[i]);
}
List<List<Integer>> ans = new ArrayList<>();
for (int i = 0; i < n - 1; ++i) {
if (arr[i + 1] - arr[i] == mi) {
ans.add(List.of(arr[i], arr[i + 1]));
}
}
return ans;
}
}
class Solution {
public:
vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
sort(arr.begin(), arr.end());
int mi = 1 << 30;
int n = arr.size();
for (int i = 0; i < n - 1; ++i) {
mi = min(mi, arr[i + 1] - arr[i]);
}
vector<vector<int>> ans;
for (int i = 0; i < n - 1; ++i) {
if (arr[i + 1] - arr[i] == mi) {
ans.push_back({arr[i], arr[i + 1]});
}
}
return ans;
}
};
func minimumAbsDifference(arr []int) (ans [][]int) {
sort.Ints(arr)
mi := 1 << 30
n := len(arr)
for i := 0; i < n-1; i++ {
if t := arr[i+1] - arr[i]; t < mi {
mi = t
}
}
for i := 0; i < n-1; i++ {
if arr[i+1]-arr[i] == mi {
ans = append(ans, []int{arr[i], arr[i+1]})
}
}
return
}
function minimumAbsDifference(arr: number[]): number[][] {
arr.sort((a, b) => a - b);
let mi = 1 << 30;
const n = arr.length;
for (let i = 0; i < n - 1; ++i) {
mi = Math.min(mi, arr[i + 1] - arr[i]);
}
const ans: number[][] = [];
for (let i = 0; i < n - 1; ++i) {
if (arr[i + 1] - arr[i] === mi) {
ans.push([arr[i], arr[i + 1]]);
}
}
return ans;
}