2022-01-28: for example, {5, 3, 1, 4} all number pairs are: (5,3), (5,1)

2022-01-28： such as { 5, 3, 1, 4 }

All numbers yes ：(5,3)、(5,1)、(5,4)、(3,1)、(3,4)、(1,4)

The absolute value of the difference between pairs of numbers ： 2、4、1、2、1、3

The absolute value of the difference is sorted ：1、1、2、2、3、4

Given an array arr, And a positive number k

return arr The absolute value of the difference between all numbers in the , The first k How much is the small one

arr = { 5, 3, 1, 4 }, k = 4

return 2

answer 2022-01-28：

Sort + Two points + No regression .

Time complexity ：O(log( Big - Small ))*O(N).

Spatial complexity ：O(1).

The code to use golang To write . The code is as follows ：

package main

import (
    "fmt"
    "sort"
)

func main() {
    fmt.Println(kthABS2([]int{5, 3, 1, 4}, 4))
}

//  Two points  +  No regression 
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 ~  Big - Small   Two points 
    // l  ~  r
    left := 0
    right := arr[n-1] - arr[0]
    mid := 0
    rightest := -1
    for left <= right {
        mid = (left + right) / 2
        //  The absolute value of the difference between numbers <=mid Number of digit pairs , Is it right?  < k One of the ！
        if valid(arr, mid, k) {
            rightest = mid
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return rightest + 1
}

//  hypothesis arr All number pairs in , Absolute value of the difference <=limit The number of x
//  If  x < k, Up to standard , return true
//  If  x >= k, Substandard , return 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
    }
}

The results are as follows ：

picture

Zuo Shen java Code