The Minimum Absolute Difference Algorithm of an Array
- 时间:2020-09-19 10:45:07
- 分类:网络文摘
- 阅读:107 次
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 arrExample 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^6Hints:
Find the minimum absolute difference between two elements in the array.
The minimum absolute difference must be a difference between two consecutive elements in the sorted array.
Finding Minimum Absolute Difference in a Sorted Array
Of course, we can bruteforce the array for each possible pair, and then we can compare and record the minimum pairs that have the smallest absolute difference values. However, this cost O(N^2), which is not the most efficient algorithm.
If we sort the array (which we can, in O(NLogN) time), then we can do another O(N) loop to compare only the adjacent elements because there is no need to compare non-neighbour pairs as they will not be the smallest minimum absolute difference pair.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | class Solution { public: vector<vector<int>> minimumAbsDifference(vector<int>& arr) { vector<vector<int>> r; sort(begin(arr), end(arr)); int D = INT_MAX; for (int i = 1; i < arr.size(); ++ i) { int d = arr[i] - arr[i - 1]; if (d < D) { r.clear(); D = d; r.push_back({arr[i - 1], arr[i]}); } else if (d == D) { r.push_back({arr[i - 1], arr[i]}); } } return r; } }; |
class Solution { public: vector<vector<int>> minimumAbsDifference(vector<int>& arr) { vector<vector<int>> r; sort(begin(arr), end(arr)); int D = INT_MAX; for (int i = 1; i < arr.size(); ++ i) { int d = arr[i] - arr[i - 1]; if (d < D) { r.clear(); D = d; r.push_back({arr[i - 1], arr[i]}); } else if (d == D) { r.push_back({arr[i - 1], arr[i]}); } } return r; } };
Then, if the current difference value is smaller, then we clear the result vector, record the minimum value, and push the current pair. If we find a equal pair, we simply push it to the back of the result vector. O(1) constant space is required.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:饮食安全:隔夜食物危害到底有多大? 市场上的“非油炸”食品真没油吗 包装上宣称“无糖”的食品真没糖吗 号称“零脂肪”的乳品同样会引发肥胖 宣称“高钙”的食品补钙效果未必好 广告中的“高膳食纤维”食品并不健康 宣传的“零热量”饮品真的很不靠谱 宣称健康的“全谷物”饮品营养仅一般 国家食品药品监督管理总局正式挂牌 办公室白领防电脑辐射食品大盘点
- 评论列表
-
- 添加评论