【Day 41 】2024-05-18 - 822. Kth-Pair-Distance

[azl397985856]

822. Kth-Pair-Distance

入选理由

暂无

题目地址

https://binarysearch.com/problems/Kth-Pair-Distance

前置知识

暂无

题目描述

Given a list of integers nums and an integer k, return the k-th (0-indexed) smallest abs(x - y) for every pair of elements (x, y) in nums. Note that (x, y) and (y, x) are considered the same pair.

Constraints

n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [1, 5, 3, 2]
k = 3
Output
2
Explanation
Here are all the pair distances:

abs(1 - 5) = 4
abs(1 - 3) = 2
abs(1 - 2) = 1
abs(5 - 3) = 2
abs(5 - 2) = 3
abs(3 - 2) = 1
Sorted in ascending order we have [1, 1, 2, 2, 3, 4].

[zhiyuanpeng]

class Solution: def solve(self, A, k): A.sort() def count_not_greater(diff): i = ans = 0 for j in range(1, len(A)): while A[j] - A[i] > diff: i += 1 ans += j - i return ans l, r = 0, A[-1] - A[0] k += 1 # zero based -> one based while l <= r: mid = (l + r) // 2 if count_not_greater(mid) >= k: r = mid - 1 else: l = mid + 1 return l

[Yukibei]

class Solution { public: int findRadius(vector &houses, vector &heaters) { int ans = 0; sort(heaters.begin(), heaters.end()); for (int house: houses) { int j = upper_bound(heaters.begin(), heaters.end(), house) - heaters.begin(); int i = j - 1; int rightDistance = j >= heaters.size() ? INT_MAX : heaters[j] - house; int leftDistance = i < 0 ? INT_MAX : house - heaters[i]; int curDistance = min(leftDistance, rightDistance); ans = max(ans, curDistance); } return ans; } };

[Dtjk]

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