719. Find K-th Smallest Pair Distance
Đề Bài
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
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(log n)
💾 Không gian
O(n)
Lời Giải
C++
0719-find-k-th-smallest-pair-distance.cpp
class Solution {
private:
vector<int> nums;
int k;
public:
int smallestDistancePair(vector<int>& nums, int k) {
const int n = nums.size();
this->nums = nums;
this->k = k;
sort(nums.begin(), nums.end());
int left = 0;
int right = nums[n - 1] - nums[0];
int ans = 0;
while (left <= right) {
int mid = (left + right) / 2;
int cnt = 0;
for (int i = 0, j = 0; i < n; ++i) {
while (j < n && nums[i] - nums[j] > mid) {
j++;
}
cnt += i - j;
}
cout << mid << ' ' << cnt << '\n';
if (cnt >= k) {
ans = mid;
right = mid - 1;
}
else {
left = mid + 1;
}
}
return ans;
}
};
Python
0719-find-k-th-smallest-pair-distance.py
class Solution:
def smallestDistancePair(self, nums: List[int], k: int) -> int:
nums.sort()
n = len(nums)
left, right = 0, 10**9
ans = right
def get_len(diff):
glen = 0
j = 0
for i in range(n):
while nums[i] - nums[j] > diff:
j += 1
glen += i - j
return glen
while left <= right:
mid = (left + right) // 2
if get_len(mid) < k:
left = mid + 1
else:
ans = mid
right = mid - 1
return ans