leetcode:1200. Minimum absolute difference

1200. Minimum absolute difference

source ： Power button （LeetCode）

link : https://leetcode.cn/problems/minimum-absolute-difference

Here's an array of integers arr, Each of these elements is inequality .
Please find all the elements with the least absolute difference , And return in ascending order .

Example 1：

 Input ：arr = [4,2,1,3]
 Output ：[[1,2],[2,3],[3,4]]

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

Tips ：

• 2 <= arr.length <= $10^5$
• $-10^6$ <= arr[i] <= $10^6$

solution

• Sort + Traverse : The difference between adjacent elements after sorting is the smallest absolute difference of the element , Traverse after sorting , If the absolute difference is less than the minimum absolute difference , Update absolute difference , Update results ; If it is equal to the minimum absolute difference , Add one result to the result ; If it is larger than, it will not be processed ;

Code implementation

Sort + Traverse

python Realization

class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        n = len(arr)
        res = []
        arr.sort()
        min_diff = float('inf')
        for i in range(1, n):
            if arr[i] - arr[i-1] < min_diff:
                res = [[arr[i-1], arr[i]]]
                min_diff = arr[i] - arr[i-1]
            elif arr[i] - arr[i-1] == min_diff:
                res.append([arr[i-1], arr[i]])
        return res

c++ Realization

class Solution {
    
public:
    vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
    
        int n = arr.size();
        vector<vector<int>> res;
        sort(arr.begin(), arr.end());

        int min_diff = INT_MAX;

        for (int i=1; i<n; i++) {
    
            if (arr[i]-arr[i-1] < min_diff){
    
                res = {
    {
    arr[i-1], arr[i]}};
                min_diff = arr[i] - arr[i-1];
            }

            else if (arr[i]-arr[i-1] == min_diff)
                res.push_back({
    arr[i-1], arr[i]});
        }
        return res;
    }
};

Complexity analysis

• Time complexity ： $O(NlogN)$ Sorting time
• Spatial complexity ： $O(logN)$ Space required for sorting