Description
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
Solutions
Solution 1
PythonJavaC++GoTypeScriptJavaScript
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)(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
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;
}(code-box)
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
function smallestDistancePair(nums, k) {
nums.sort((a, b) => a - b);
const n = nums.length;
let left = 0,
right = nums[n - 1] - nums[0];
while (left < right) {
const mid = (left + right) >> 1;
let count = 0,
i = 0;
for (let j = 0; j < n; j++) {
while (nums[j] - nums[i] > mid) {
i++;
}
count += j - i;
}
if (count >= k) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}(code-box)
