一堆数字中两两间距离中排第K小的是多少。找第K小的常见解法有排序（快排或heap sort）和二分范围。这道题用前者需要O(N^2)遍历 + O(N^2lg(N^2))排序。二分范围的话需要O(NlgW)再加上对所有数排序的时间O(NlgN)，W是范围。因为是对W取log，即使W很大所需通常时间相比N来说也会小很多。因此二分范围，每次对mid所代表的候选距离数对每个j，数有多少个i和j的距离小于mid，然后和K比较。
/*
* @lc app=leetcode id=719 lang=cpp
*
* [719] Find K-th Smallest Pair Distance
*
* https://leetcode.com/problems/find-k-th-smallest-pair-distance/description/
*
* algorithms
* Hard (29.72%)
* Likes: 625
* Dislikes: 21
* Total Accepted: 23K
* Total Submissions: 76.7K
* Testcase Example: '[1,3,1]\n1'
*
* 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 .
* 0 .
* 1 .
*
*
*/
// @lc code=start
class Solution {
public:
int smallestDistancePair(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int N = nums.size(), start = 0, end = nums.back() - nums[0];
while (start < end) {
int mid = start + (end - start) / 2, i = 0, cnt = 0;
for (int j = 0; j < N; ++j) {
while (i < N && nums[j] - nums[i] > mid) ++i;
cnt += j - i;
}
if (cnt < k) start = mid + 1;
else end = mid;
}
return start;
}
};
// @lc code=end