当前位置：首页 > article >正文

719.找出第K小的数对距离（双指针、K值问题）

article 2025/1/27 13:07:51

题目

数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。

给你一个整数数组 nums 和一个整数 k ，数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length 。返回所有数对距离中第 k 小的数对距离。

过程

思路1：列举，然后双指针两端搜索收敛最小值。
思路2：双指针，两端往中心搜索.先进行排序。
在看到k值问题时我们比较容易想到堆，再一个便是二分。

解法

class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int n = nums.size(), left = 0, right = nums.back() - nums.front();
        while (left <= right) {
            int mid = (left + right) / 2;
            int cnt = 0;
            for (int i = 0, j = 0; j < n; j++) {
                while (nums[j] - nums[i] > mid) {
                    i++;
                }
                cnt += j - i;
            }
            if (cnt >= k) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};