719. Find K-th Smallest Pair Distance
## 思路
兩數差的範圍是[0, max(nums) - min(nums)]
用 binary search 搜答案, 檢查配對數是否超過k個
檢查的函式: 數列sort過後, 用two pointer計算
## Code
```python
class Solution:
def smallestDistancePair(self, nums: List[int], k: int) -> int:
nums.sort()
n = len(nums)
def check(val):
count = right = 0
for left in range(n):
while right < n and nums[right] - nums[left] <= val:
# (nums[i], nums[right]) i: left~right-1
count += (right - left)
right += 1
return count >= k
res = 0
left, right = 0, nums[-1] - nums[0]
while left <= right:
mid = (left + right) // 2
if check(mid):
res = mid
right = mid - 1
else:
left = mid + 1
return res
```
--
http://i.imgur.com/OLvBn3b.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.151 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723604966.A.6DF.html