719. find the distance of the number pair with the smallest K (two points)

Number pair (a,b) By integer a and b form , The number pair distance is defined as a and b The absolute difference between .

Give you an array of integers nums And an integer k , Number pair by nums[i] and nums[j] Constitute and satisfy 0 <= i < j < nums.length . return All pairs of distances The first k Small number pair distance .

Example 1：

Input ：nums = [1,3,1], k = 1
Output ：0
explain ： The number pairs and the corresponding distances are as follows ：
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
Distance No 1 A small number pair is (1,1) , A distance of 0 .
Example 2：

Input ：nums = [1,1,1], k = 2
Output ：0
Example 3：

Input ：nums = [1,6,1], k = 3
Output ：5

class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        //  Sort service enumeration interval 
        sort(nums.begin(), nums.end());
        int left = 0, right = nums[nums.size() - 1], n = nums.size();
        while(left < right){
            int mid = (left + right) >> 1, cnt = 0;
            //  Enumeration interval 
            for(int i = 0, j = 0; i < n; ++i){
                //  Find the first one that doesn't meet the condition j
                while(j < n && nums[j] - nums[i] <= mid) ++j;
                cnt += j - i - 1;
            }
            //  Determine bisection direction 
            if(cnt < k)
                left = mid + 1;
            else
                right = mid;
        }
        return left;
    }
};