1200.Minimum Absolute Difference

The description of the problem

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 parirs in ascending order (with respect to pairs), each pair [a, b] follows.
1. a, b are from arr
2. a < b
3. b - a equals to the minimum absolute difference of any two elements in arr.

an example

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.

 source ： Power button （LeetCode）
 link ：https://leetcode.cn/problems/minimum-absolute-difference

The solution 1

The intuition

Leverage the loop nesting to traveral all the diffVal and store them into a map and log the minimum difference value. In the end, sort out the return nesting loop.

The corresponding codes

#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>
#include <map>
using namespace std;
class Solution {
    
public:
    vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
    
        vector<vector<int>> res;
        map<int, vector<vector<int>>> m;
        int minDiff = INT_MAX;
        for (int i = 0; i < arr.size(); i++) {
    
            for (int j = i + 1; j < arr.size(); j++) {
    
                int diff = abs(arr[i] - arr[j]);
                minDiff = min(minDiff, diff);
                vector<int> t;
                if (arr[i] < arr[j]) {
    
                    t.push_back(arr[i]);
                    t.push_back(arr[j]);
                } else {
    
                    t.push_back(arr[j]);
                    t.push_back(arr[i]);
                }
                m[diff].push_back(t);
            }
        }
        res = m[minDiff];
        // sort res by first element
        sort(res.begin(), res.end(), [](vector<int>& a, vector<int>& b) {
    
            return a[0] < b[0];
        });
        return res;
        
    }
};
int main() 
{
    
    Solution s;
    vector<int> arr = {
    4, 2, 1, 3};
    vector<vector<int>> res = s.minimumAbsDifference(arr);
    for (auto& v : res) {
    
        for (auto& i : v) {
    
            cout << i << " ";
        }
        cout << endl;
    }
    return 0;
}

The result

The solution 2

firstly sort out the elements in arr in asecending order. traversal the arr to find the minimum difference value. Lastly, traversal the second time.

The codes

#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>
#include <map>
using namespace std;
class Solution {
    
public:
    vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
    
        vector<vector<int>> res;
        int minDiff = INT_MAX;
        sort(arr.begin(), arr.end());
        for (int i = 0; i < arr.size() - 1; i++) {
    
            int diff = arr[i + 1] - arr[i];
            minDiff = min(minDiff, diff);
        }
        for (auto it = arr.begin(); it != arr.end() - 1; it++) {
    
            if (abs(*(it + 1) - *it) == minDiff) {
    
                res.push_back({
    *it, *(it + 1)});
            }
        }
        return res;
    }
};
int main() 
{
    
    Solution s;
    vector<int> arr = {
    4, 2, 1, 3};
    vector<vector<int>> res = s.minimumAbsDifference(arr);
    for (auto& v : res) {
    
        for (auto& i : v) {
    
            cout << i << " ";
        }
        cout << endl;
    }
    return 0;
}

The corresponding results

The more optimized solution

#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>
#include <map>
using namespace std;
class Solution {
    
public:
    vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
    
        vector<vector<int>> res;
        int minDiff = INT_MAX;
        sort(arr.begin(), arr.end());
        for (int i = 0; i < arr.size() - 1; i++) {
    
            int diff = arr[i + 1] - arr[i];
            if (diff < minDiff) {
    
                minDiff = diff;
                res.clear();
                res.push_back({
    arr[i], arr[i + 1]});
            } else if (diff == minDiff) {
    
                res.push_back({
    arr[i], arr[i + 1]});
            }
        }
        return res;
    }
};
int main() 
{
    
    Solution s;
    vector<int> arr = {
    4, 2, 1, 3};
    vector<vector<int>> res = s.minimumAbsDifference(arr);
    for (auto& v : res) {
    
        for (auto& i : v) {
    
            cout << i << " ";
        }
        cout << endl;
    }
    return 0;
}

The corresponding result