2022-01-28：比如{ 5, 3, 1, 4 }
全部数字对是：(5,3)、(5,1)、(5,4)、(3,1)、(3,4)、(1,4)
数字对的差值绝对值： 2、4、1、2、1、3
差值绝对值排序后：1、1、2、2、3、4
给定一个数组arr，和一个正数k
返回arr中所有数字对差值的绝对值，第k小的是多少
arr = { 5, 3, 1, 4 }, k = 4
返回2
答案2022-01-28：
排序 二分 不回退。
时间复杂度：O(log(大-小))*O(N)。
空间复杂度：O(1)。
代码用golang编写。代码如下：
package main
import (
"fmt"
"sort"
)
func main() {
fmt.Println(kthABS2([]int{5, 3, 1, 4}, 4))
}
// 二分 不回退
func kthABS2(arr []int, k int) int {
n := len(arr)
if n < 2 || k < 1 || k > ((n*(n-1))>>1) {
return -1
}
sort.Ints(arr)
// 0 ~ 大-小 二分
// l ~ r
left := 0
right := arr[n-1] - arr[0]
mid := 0
rightest := -1
for left <= right {
mid = (left right) / 2
// 数字对差值的绝对值<=mid的数字对个数，是不是 < k个的！
if valid(arr, mid, k) {
rightest = mid
left = mid 1
} else {
right = mid - 1
}
}
return rightest 1
}
// 假设arr中的所有数字对，差值绝对值<=limit的个数为x
// 如果 x < k，达标，返回true
// 如果 x >= k，不达标，返回false
func valid(arr []int, limit, k int) bool {
x := 0
for l, r := 0, 1; l < len(arr); r = getMax(r, l) {
for r < len(arr) && arr[r]-arr[l] <= limit {
r
}
x = r - l - 1
l
}
return x < k
}
func getMax(a, b int) int {
if a > b {
return a
} else {
return b
}
}
执行结果如下：
***
[左神java代码](https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class48/Code01_MinKthPairMinusABS.java)
,
