class Solution {
public:
int smallestDistancePair(vector<int>& nums, int k) {
}
};
719. 找出第 K 小的数对距离
数对 (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原站题解
java 解法, 执行用时: 5 ms, 内存消耗: 41.4 MB, 提交时间: 2023-04-02 12:35:18
class Solution {
public int smallestDistancePair(int[] nums, int k) {
Arrays.sort(nums);
int n = nums.length, left = 0, right = nums[n - 1] - nums[0];
while (left <= right) {
int mid = (left + right) / 2;
int cnt = 0;
for (int i = 0, j = 0; j < n; j++) {
while (nums[j] - nums[i] > mid) {
i++;
}
cnt += j - i;
}
if (cnt >= k) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
}
golang 解法, 执行用时: 16 ms, 内存消耗: 3.2 MB, 提交时间: 2023-04-02 12:35:01
func smallestDistancePair(nums []int, k int) int {
sort.Ints(nums)
return sort.Search(nums[len(nums)-1]-nums[0], func(mid int) bool {
cnt := 0
for j, num := range nums {
i := sort.SearchInts(nums[:j], num-mid)
cnt += j - i
}
return cnt >= k
})
}
golang 解法, 执行用时: 4 ms, 内存消耗: 3.2 MB, 提交时间: 2023-04-02 12:34:54
func smallestDistancePair(nums []int, k int) int {
sort.Ints(nums)
return sort.Search(nums[len(nums)-1]-nums[0], func(mid int) bool {
cnt, i := 0, 0
for j, num := range nums {
for num-nums[i] > mid {
i++
}
cnt += j - i
}
return cnt >= k
})
}
python3 解法, 执行用时: 72 ms, 内存消耗: 15.9 MB, 提交时间: 2023-04-02 12:34:35
class Solution:
def smallestDistancePair(self, nums: List[int], k: int) -> int:
def count(mid: int) -> int:
cnt = i = 0
for j, num in enumerate(nums):
while num - nums[i] > mid:
i += 1
cnt += j - i
return cnt
nums.sort()
return bisect_left(range(nums[-1] - nums[0]), k, key=count)
python3 解法, 执行用时: 108 ms, 内存消耗: 15.9 MB, 提交时间: 2023-04-02 12:34:27
class Solution:
def smallestDistancePair(self, nums: List[int], k: int) -> int:
def count(mid: int) -> int:
cnt = 0
for j, num in enumerate(nums):
i = bisect_left(nums, num - mid, 0, j)
cnt += j - i
return cnt
nums.sort()
return bisect_left(range(nums[-1] - nums[0]), k, key=count)