Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/719.html
719. Find K-th Smallest Pair Distance (Hard)
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:
2 <= len(nums) <= 10000.0 <= nums[i] < 1000000.1 <= k <= len(nums) * (len(nums) - 1) / 2.
Related Topics:
Array, Binary Search, Heap
Similar Questions:
- Find K Pairs with Smallest Sums (Medium)
- Kth Smallest Element in a Sorted Matrix (Medium)
- Find K Closest Elements (Medium)
- Kth Smallest Number in Multiplication Table (Hard)
- K-th Smallest Prime Fraction (Hard)
Solution 1. Binary Answer
// OJ: https://leetcode.com/problems/find-k-th-smallest-pair-distance/
// Time: O(NlogN + NlogNlogD) where D is the distance between the minimal distance and the maximal distance.
// Space: O(1)
class Solution {
int count(vector<int> &A, int M) {
int cnt = 0;
for (int i = 0; i < A.size(); ++i) cnt += upper_bound(begin(A), end(A), A[i] + M) - begin(A) - i - 1;
return cnt;
}
public:
int smallestDistancePair(vector<int>& A, int k) {
sort(begin(A), end(A));
int L = INT_MAX, R = A.back() - A[0];
for (int i = 1; i < A.size(); ++i) L = min(L, A[i] - A[i - 1]);
while (L <= R) {
int M = (L + R) / 2, cnt = count(A, M);
if (cnt < k) L = M + 1;
else R = M - 1;
}
return L;
}
};
Solution 2.
We can reduce the time complexity of count function from O(NlogN) to O(N).
// OJ: https://leetcode.com/problems/find-k-th-smallest-pair-distance/
// Time: O(NlogN + NlogD) where D is the distance between the minimal distance and the maximal distance.
// Space: O(1)
class Solution {
int count(vector<int> &A, int M) {
int cnt = 0, i = 0, j = 0, N = A.size();
while (i < N) {
while (j < N && A[j] - A[i] <= M) ++j;
cnt += j - i - 1;
++i;
}
return cnt;
}
public:
int smallestDistancePair(vector<int>& A, int k) {
sort(begin(A), end(A));
int L = INT_MAX, R = A.back() - A[0];
for (int i = 1; i < A.size(); ++i) L = min(L, A[i] - A[i - 1]);
while (L <= R) {
int M = (L + R) / 2, cnt = count(A, M);
if (cnt < k) L = M + 1;
else R = M - 1;
}
return L;
}
};
-
class Solution { public int smallestDistancePair(int[] nums, int k) { Arrays.sort(nums); int length = nums.length; int low = 0, high = nums[length - 1] - nums[0]; while (low < high) { int mid = (high - low) / 2 + low; int count = 0, left = 0; for (int right = 0; right < length; right++) { while (nums[right] - nums[left] > mid) left++; count += right - left; } if (count >= k) high = mid; else low = mid + 1; } return low; } } ############ 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; } } -
// OJ: https://leetcode.com/problems/find-k-th-smallest-pair-distance/ // Time: O(NlogN + NlogNlogD) where D is the distance between the minimal distance and the maximal distance. // Space: O(1) class Solution { int count(vector<int> &A, int M) { int cnt = 0; for (int i = 0; i < A.size(); ++i) cnt += upper_bound(begin(A), end(A), A[i] + M) - begin(A) - i - 1; return cnt; } public: int smallestDistancePair(vector<int>& A, int k) { sort(begin(A), end(A)); int L = INT_MAX, R = A.back() - A[0]; for (int i = 1; i < A.size(); ++i) L = min(L, A[i] - A[i - 1]); while (L <= R) { int M = (L + R) / 2, cnt = count(A, M); if (cnt < k) L = M + 1; else R = M - 1; } return L; } }; -
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) -
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 } -
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; }