第 K 小的距离对

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型ArrayList
     * @param k int整型
     * @return int整型
     */
    public int kthDistance (ArrayList<Integer> nums, int k) {
        // write code here
        Collections.sort(nums);

        int n = nums.size();
        int left = 0;
        int right = nums.get(n - 1) - nums.get(0);
        int mid;
        // 二分
        while (left <= right) {
            mid = left + (right - left) / 2;
            // left最终指向第一个cnt大于等于k的数
            // if(check(nums, k, mid)){
            if (check(nums, k, mid)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    private boolean check(ArrayList<Integer> nums, int k, int target) {
        int n = nums.size();
        // 小于等于target的个数
        int cnt = 0;
        // 双指针
        for (int i = 0; i < n; i++) {
            // 再次二分 进行优化
            int left = i + 1, right = n - 1;
            int mid;
            while (left <= right) {
                mid = left + ((right - left) >> 1);
                // left最终指向第一个满足条件(nums.get(left)-nums.get(i) > target)的位置(从左往右)
                if (nums.get(mid) - nums.get(i) <= target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            cnt += left - i - 1;
            if (cnt >= k) {
                return false;
            }
        }

        return true;
    }
}