---
description: https://leetcode.com/problems/find-k-th-smallest-pair-distance/
---

# 719. Find K-th Smallest Pair Distance

一堆数字中两两间距离中排第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比较。

```cpp
/*
 * @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


```
