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
code:Example.txt
Explanation: The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.
一切ライブラリに頼らない方法(heap sort)で実装したけど、後でsort.Intsを使うとかなり高速になった code:main.go
func heapify(arr []int, n, i int) {
lgstIdx := i
l, r := i*2 + 1, i*2 + 2
lgstIdx = l
}
lgstIdx = r
}
if lgstIdx != i {
heapify(arr, n, lgstIdx)
}
}
func sort(arr []int) []int {
n := len(arr)
for i := n/2; i >= 0; i-- {
heapify(arr, n, i)
}
for i := n-1; i >= 0; i-- {
heapify(arr, i, 0)
}
return arr
}
func minimumAbsDifference(arr []int) [][]int {
n := len(arr)
if n < 3 {
return [][]int{arr}
}
sort(arr)
ret := [][]int{}
for i := 1; i < n-1; i++ {
if diff < minDiff {
minDiff = diff
}
}
for i := 0; i < n-1; i++ {
if diff == minDiff {
ret = append(ret, []int{arri, arri+1}) }
}
return ret
}