leetcode

0 class Solution {

1 int count(const vector<int> &nums, int tgt) const {

2 int res = 0;

3

4 for (int l = 0, r = 1; r < size(nums); r++) {

5 while (nums[r] - nums[l] > tgt)

6 l++;

7 res += r - l;

8 }

9

10 return res;

11 }

12

13 public:

14 int smallestDistancePair(vector<int> &nums, int k) const {

15 sort(begin(nums), end(nums));

16

17 int low = 0, high = nums.back() - nums.front();

18 while (low < high) {

19 const int mid = low + (high - low) / 2;

20 const int cnt = count(nums, mid);

21

22 if (cnt < k)

23 low = mid + 1;

24 else

25 high = mid;

26 }

27

28 return low;

29 }

30 };