數(shù)對(duì) (a,b) 由整數(shù) a 和 b 組成阁簸，其數(shù)對(duì)距離定義為 a 和 b 的絕對(duì)差值。
給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k 咖驮，數(shù)對(duì)由 nums[i] 和 nums[j] 組成且滿(mǎn)足 0 <= i < j < nums.length 边器。返回 所有數(shù)對(duì)距離中 第 k 小的數(shù)對(duì)距離训枢。
示例 1：
輸入：nums = [1,3,1], k = 1
輸出：0
解釋?zhuān)簲?shù)對(duì)和對(duì)應(yīng)的距離如下：
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
距離第 1 小的數(shù)對(duì)是 (1,1) ，距離為 0 忘巧。
示例 2：
輸入：nums = [1,1,1], k = 2
輸出：0
示例 3：
輸入：nums = [1,6,1], k = 3
輸出：5
提示：
- n == nums.length
- 2 <= n <= 10^4
- 0 <= nums[i] <= 10^6
- 1 <= k <= n * (n - 1) / 2
思路
- 由于數(shù)組的長(zhǎng)度范圍很大恒界，所以需要考慮使用二分法
- 給定距離 mid，計(jì)算所有距離小于等于 mid 的數(shù)對(duì)數(shù)目 cnt 可以使用雙指針：初始左端點(diǎn) i = 0砚嘴，我們從小到大枚舉所有數(shù)對(duì)的右端點(diǎn) j十酣，移動(dòng)左端點(diǎn)直到 nums[j]?nums[i]≤mid，那么右端點(diǎn)為 j 且距離小于等于 mid 的數(shù)對(duì)數(shù)目為 j?i际长，計(jì)算這些數(shù)目之和耸采。
方法一：排序 + 二分法 + 雙指針
public int smallestDistancePair(int[] nums, int k) {
Arrays.sort(nums);
int left = 0, right = nums[nums.length - 1] - nums[0], ans = 0;
while (left <= right) {
int mid = (right + left) / 2;
int cnt = 0;
for (int i = 0, j = 0; j < nums.length; j++) {
while (nums[j] - nums[i] > mid) {
i++;
}
cnt += j - i;
}
if (cnt >= k) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
正常雙重遍歷 + 優(yōu)先隊(duì)列（內(nèi)存超出限制）
class Solution {
public int smallestDistancePair(int[] nums, int k) {
PriorityQueue<Integer> queue = new PriorityQueue();
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
queue.add(Math.abs(nums[i] - nums[j]));
}
}
int ans = -1;
while (k > 0 && !queue.isEmpty()) {
ans = queue.poll();
k--;
}
return ans;
}
}
這種寫(xiě)法，僅供參考工育，在leetcode上通不過(guò)虾宇。報(bào)內(nèi)存超出限制
作者：LeetCode-Solution
鏈接：https://leetcode.cn/problems/find-k-th-smallest-pair-distance/solution/zhao-chu-di-k-xiao-de-shu-dui-ju-chi-by-xwfgf/
來(lái)源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)如绸，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處嘱朽。
