Hard
Related Topics: Array / Two Pointers / Binary Search / Sorting
LeetCode Source

解題想法

題目是要求我們找到第 k 小的對

而此對必須由 nums 組成

此題是用 binary search 去解

在進行 binary search 之前我們必須先將 nums 排序

之後定義 left 和 right 為 0 和最大元素建去最小元素的值

接著開始透過 mid = (right - left) / 2 找猜測此值是第幾小的對

count_pairs 會紀錄說目前此猜測值是第幾小的值

回傳 count 與 k 比較

如果 count < k 則 left = mid + 1

否則 right = m

而最後 left 就是第 k 小的對之值

Complexity

Time Complexity: O(nlogn)
Space Complexity: O(n)

Python

class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        nums.sort()

        def count_pairs(guess: int) -> int:
            count = 0
            j = 0
            for i in range(len(nums)):
                while j < len(nums) and nums[j] - nums[i] <= guess:
                    j += 1
                count += j - i - 1
            return count

        left, right = 0, nums[-1] - nums[0]
        while left < right:
            mid = (left + right) // 2
            if count_pairs(mid) < k:
                left = mid + 1
            else:
                right = mid
        return left

C++

vector.front() 會回傳第一個元素

vector.end() 會回傳最後一個元素

class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());

        int l = 0, r = nums.back() - nums.front();

        while (l < r) {
            int m = l + (r - l) / 2;
            if (count_pairs(nums, m) < k)
                l = m + 1;
            else
                r = m;
        }
        return l;
    }

    int count_pairs(vector<int>& nums, int guess) {
        int count = 0, j = 0;
        for (int i = 0; i < nums.size(); i++) {
            while (j < nums.size() && (nums[j] - nums[i] <= guess))
                j += 1;
            count += j - i - 1;
        }
        return count;
    }
};