# 719. Find K-th Smallest Pair Distance

Given an integer array, return the k-th smallest distance among all the pairs. The distance of a pair (A, B) is defined as the absolute difference between A and B.

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.
``````

Note:

1. `2 <= len(nums) <= 10000`.
2. `0 <= nums[i] < 1000000`.
3. `1 <= k <= len(nums) * (len(nums) - 1) / 2`.

``````class Solution {
public:
int smallestDistancePair(vector<int>& nums, int k) {
int n = nums.size(), N = 1000000;
vector<int> cnt(N, 0);
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
++cnt[abs(nums[i] - nums[j])];
}
}
for (int i = 0; i < N; ++i) {
if (cnt[i] >= k) return i;
k -= cnt[i];
}
return -1;
}
};
``````

1    2    3    3    5

start              i

mid = 2

``````class Solution {
public:
int smallestDistancePair(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int n = nums.size(), left = 0, right = nums.back() - nums[0];
while (left < right) {
int mid = left + (right - left) / 2, cnt = 0, start = 0;
for (int i = 0; i < n; ++i) {
while (start < n && nums[i] - nums[start] > mid) ++start;
cnt += i - start;
}
if (cnt < k) left = mid + 1;
else right = mid;
}
return right;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/719

Find K Pairs with Smallest Sums

Kth Smallest Element in a Sorted Matrix

Find K Closest Elements

Kth Smallest Number in Multiplication Table

K-th Smallest Prime Fraction

https://leetcode.com/problems/find-k-th-smallest-pair-distance/solution/

https://leetcode.com/problems/find-k-th-smallest-pair-distance/discuss/109077/C++-counting-sort-O(n2)-and-binary-search-O(nlogn)

https://leetcode.com/problems/find-k-th-smallest-pair-distance/discuss/109082/Approach-the-problem-using-the-%22trial-and-error%22-algorithm

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation