Leetcode - Minimum Absolute Difference

https://leetcode.com/problems/minimum-absolute-difference/

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 arr

Constraints:

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

Firstly, I'm considering a count sort. But the data range is too big(10^6). So sort it and then find the min distance between two consecutive elements and store the pair.

Time complexity: O(nlogn)

func minimumAbsDifference(arr []int) [][]int {
    sort.Ints(arr)
    min := math.MaxInt32
    for i := 1; i < len(arr); i++ {
        if min > arr[i] - arr[i-1] {
            min = arr[i] - arr[i-1]
        }
    }
    result := [][]int{}
    for i := 1; i < len(arr); i++ {
        if arr[i] - arr[i-1] == min {
            result = append(result, []int{arr[i-1], arr[i]})
        }
    }
    return result
}

• 相关文章
• 全局相关文章