0719. Find K-th Smallest Pair Distance¶
题目信息¶
- 题号:
0719
- 难度:
Hard
- 主题:
数组、数对距离、顺序统计
- 原题:
- 重点:
数对由不同下标
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 小距离,两个元素也分别取到允许的最小值和最大值。