代码拉取完成，页面将自动刷新
同步操作将从 doocs/leetcode 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。
给你一个整数数组 nums 和一个整数 k ，数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length 。返回 所有数对距离中 第 k 小的数对距离。
示例 1：
输入：nums = [1,3,1], k = 1 输出：0 解释：数对和对应的距离如下： (1,3) -> 2 (1,1) -> 0 (3,1) -> 2 距离第 1 小的数对是 (1,1) ，距离为 0 。
示例 2：
输入：nums = [1,1,1], k = 2 输出：0
示例 3：
输入：nums = [1,6,1], k = 3 输出：5
提示：
n == nums.length2 <= n <= 1040 <= nums[i] <= 1061 <= k <= n * (n - 1) / 2方法一：排序 + 二分查找
先对 $nums$ 数组进行排序，然后在 $[0, nums[n-1]-nums[0]]$ 范围内二分枚举数对距离 $dist$，若 $nums$ 中数对距离小于等于 $dist$ 的数量 $cnt$ 大于等于 $k$，则尝试缩小 $dist$，否则尝试扩大 $dist$。
时间复杂度 $O(nlogn×logm)$，其中 $n$ 表示 $nums$ 的长度，$m$ 表示 $nums$ 中两个数的最大差值。
class Solution:
def smallestDistancePair(self, nums: List[int], k: int) -> int:
def count(dist):
cnt = 0
for i, b in enumerate(nums):
a = b - dist
j = bisect_left(nums, a, 0, i)
cnt += i - j
return cnt
nums.sort()
return bisect_left(range(nums[-1] - nums[0]), k, key=count)
class Solution {
public int smallestDistancePair(int[] nums, int k) {
Arrays.sort(nums);
int left = 0, right = nums[nums.length - 1] - nums[0];
while (left < right) {
int mid = (left + right) >> 1;
if (count(mid, nums) >= k) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private int count(int dist, int[] nums) {
int cnt = 0;
for (int i = 0; i < nums.length; ++i) {
int left = 0, right = i;
while (left < right) {
int mid = (left + right) >> 1;
int target = nums[i] - dist;
if (nums[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
cnt += i - left;
}
return cnt;
}
}
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;
}
class Solution {
public:
int smallestDistancePair(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int left = 0, right = nums.back() - nums.front();
while (left < right) {
int mid = (left + right) >> 1;
if (count(mid, k, nums) >= k)
right = mid;
else
left = mid + 1;
}
return left;
}
int count(int dist, int k, vector<int>& nums) {
int cnt = 0;
for (int i = 0; i < nums.size(); ++i) {
int target = nums[i] - dist;
int j = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
cnt += i - j;
}
return cnt;
}
};
func smallestDistancePair(nums []int, k int) int {
sort.Ints(nums)
n := len(nums)
left, right := 0, nums[n-1]-nums[0]
count := func(dist int) int {
cnt := 0
for i, v := range nums {
target := v - dist
left, right := 0, i
for left < right {
mid := (left + right) >> 1
if nums[mid] >= target {
right = mid
} else {
left = mid + 1
}
}
cnt += i - left
}
return cnt
}
for left < right {
mid := (left + right) >> 1
if count(mid) >= k {
right = mid
} else {
left = mid + 1
}
}
return left
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。
马建仓 AI 助手
