Leetcode - Array Transformation
Leetcode - Check If N and Its Double Exist

Leetcode - Minimum Absolute Difference

violet posted @ Apr 02, 2020 06:07:17 AM in 算法 with tags Algorithm array Golang , 213 阅读

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
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter