719. 找出第 K 小的數對

思路

在一個數組中，隨便選兩個數字nums[i]，nums[j]，其中i < j，
兩數之間的距離是nums[j] - nums[i]，請找出距離第 $k$ 小的數對。

1. 直接找到第 $k$ 小的數對很難。
2. 當距離限制 $limit$ 越寬鬆，就有越多數對滿足 $nums[j]-nums[i]\leq{limit}$ 。

根據前兩點，能對答案二分，為了做到這一點，先對數組排序，好計算滿足條件的數對。
最寬鬆的距離限制，是數組的最大值減去最小值 $\max(nums)-\min(nums)$ 。

程式碼

二分搜索

class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        int n = nums.size();
        ranges::sort(nums);

        auto check = [&](int mxDist) -> int {
            int cnt = 0;
            for(int i = 0, j = 0; i < n; i++) { // 固定左邊，盡量延伸右邊
                while(j < n && nums[j] - nums[i] <= mxDist) {
                    j++;
                }
                // 對固定左邊界 i 來說，右邊的數字 j 可以選 i+1, i+2 ... j-1, 共 j - i 對
                cnt += j - i - 1;
            }
            // 給定的距離限制下，一共有多少對數字滿足條件
            // 假如數字太少，答案會在 mxDist 更大的限制中存在
            return cnt;
        };

        // 閉區間
        int left = 0, right = nums.back() - nums[0];
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(check(mid) < k) { // 在 mid 限制下, 滿足條件的對數 < k, 表示要放開限制, 才能找到第 k 對
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        return left;
    }
};

複雜度分析

• 時間複雜度：$O(n\log{n})$
• 空間複雜度：$O(1)$