2022-01-28：比如{ 5, 3, 1, 4 } 全部数字对是：(5,3)、(5,1)、

原创

福大大架构师每日一题

发布于 2022-01-28 21:56:06

1570

发布于 2022-01-28 21:56:06

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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
    }
}

执行结果如下：