0719. Find K-th Smallest Pair Distance

题目信息

题号:

0719

难度:

Hard

主题:

数组、数对距离、顺序统计

原题:

LeetCode 0719

重点:

数对由不同下标 i < j 确定,距离为两值之差的绝对值;所有下标对的距离保留重复并按升序取第 k 个

题目重述

给定整数数组 nums 和正整数 k。对每一组满足 0 <= i < j < nums.length 的下标,定义对应数对的距离为 abs(nums[i] - nums[j])。

把全部 n * (n - 1) / 2 个下标对的距离按非递减顺序排列,返回其中第 k 小的距离。k 从 1 开始计数;不同下标对即使得到相同距离,也要作为多个元素分别参与排名。

数组长度 n 在 [2, 10^4] 范围内,0 <= nums[i] <= 10^6,并且 1 <= k <= n * (n - 1) / 2。

自建示例

重复距离按下标对分别计数:

输入:nums = [4,1,7,1], k = 4
输出:3
解释:六个下标对的距离排序后为 [0,3,3,3,6,6],第 4 个距离是 3。

最小数组取到数值范围两端:

输入:nums = [0,1000000], k = 1
输出:1000000
解释:数组达到最小长度 2,只存在下标对 (0,1),其距离为 1000000。唯一候选同时是第 1 小距离,两个元素也分别取到允许的最小值和最大值。