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.

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.

**Example 1:**

**Note:**

`2 <= len(nums) <= 10000`

.`0 <= nums[i] < 1000000`

.`1 <= k <= len(nums) * (len(nums) - 1) / 2`

.

Let L = 1000000, N = nums.size().

The optimal solution is in O(N log L) time via binary search and linear scanning.

# Solution Find K-th Smallest Pair Distance

Convert the problem into: given X, how many pairs of numbers are greater or equals to X.

This can be done in O(N), then search X in log(L)

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
class Solution { public: int smallestDistancePair(vector<int>& nums, int k) { sort(nums.begin(), nums.end()); int l = 0, r = nums[nums.size() - 1] - nums[0]; while (r > l) { int mid = (l + r) >> 1; if (count(nums, mid) < k) { l = mid + 1; } else { r = mid; } } return r; } int count(vector<int>& nums, int mid) { int ans = 0, j = 0; for (int i = 1; i < nums.size(); ++i) { while (j < i && nums[i] - nums[j] > mid) ++j; ans += i - j; } return ans; } }; |

## Python

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
class Solution: def smallestDistancePair(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ nums = sorted(nums) l, r = 0, nums[len(nums) - 1] - nums[0] # O( log(10^6) ) while l < r: mid = (l + r) >> 1 if self.count(nums, mid) < k: l = mid + 1 else: r = mid return r def count(self, nums, mid): # O(N) cnt, j = 0, 0 for i in range(1, len(nums)): while j < i and nums[i] - nums[j] > mid: j += 1 cnt += i - j return cnt |