719. 找出第 K 小的数对距离

题目

数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。

给你一个整数数组 nums 和一个整数 k ，数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length 。返回 所有数对距离中 第 k 小的数对距离。

解法

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.front();while (left <= right) {int mid = (left + right) / 2;int cnt = 0;for (int j = 0; j < n; j++) {int i = lower_bound(nums.begin(), nums.begin() + j, nums[j] - mid) - nums.begin();cnt += j - i;}if (cnt >= k) {right = mid - 1;} else {left = mid + 1;}}return left;}
};

和之前一道题一样，查找和的范围，这会儿查找差的范围果然来了。