The distance of a pair of integers a and b is defined as the absolute difference between a and b.
Given an integer array nums and an integer k, return the kth smallest distance among all the pairs nums[i] and nums[j] where 0 <= i < j < nums.length.
Example 1:
Input: nums = [1,3,1], k = 1 Output: 0 Explanation: Here are all the pairs: (1,3) -> 2 (1,1) -> 0 (3,1) -> 2 Then the 1st smallest distance pair is (1,1), and its distance is 0.
Example 2:
Input: nums = [1,1,1], k = 2 Output: 0
Example 3:
Input: nums = [1,6,1], k = 3 Output: 5
Constraints:
n == nums.length2 <= n <= 1040 <= nums[i] <= 1061 <= k <= n * (n - 1) / 2
function smallestDistancePair(nums: number[], k: number): number {
nums.sort((a, b) => a - b);
const n = nums.length;
let left = 0,
right = nums[n - 1] - nums[0];
while (left < right) {
let mid = (left + right) >> 1;
let count = 0,
i = 0;
for (let j = 0; j < n; j++) {
// 索引[i, j]距离nums[j]的距离<=mid
while (nums[j] - nums[i] > mid) {
i++;
}
count += j - i;
}
if (count >= k) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}