The Minimum Absolute Difference Algorithm of an Array
- 时间:2020-09-19 10:45:07
- 分类:网络文摘
- 阅读:111 次
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) —
推荐阅读:Algorithm to Find Duplicate Files in System using Hash Map C++ Coding Reference: Copy N values by using std::fill_n() C++ Advanced Topics: 10 Questions C++ Coding Reference: Filling a Range with a Value using std::fi How to Get List of IP addresses in BASH using hostname and tr co C++ Coding Reference: iota() – Setting Incrementing Values Javascript: From Promises to Async/Await 读《杨红樱童话》有感700字 尘缘日志:忍痛割爱 写人作文我的爷爷奶奶作文800字
- 评论列表
-
- 添加评论