719.Find K-th Smallest Pair Distance¶

719.Find K-th Smallest Pair Distance¶

Tags: Hard Binary Search Heap Array

Links: https://leetcode.com/problems/find-k-th-smallest-pair-distance/

Given an integer array, return the k-th smallest distance among all the pairs. The distance of a pair (A, B) is defined as the absolute difference between A and B.

Example 1:

Input:
nums = [1,3,1]
k = 1
Output: 0 
Explanation:
Here are all the pairs:
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
Then the 1st smallest distance pair is (1,1), and its distance is 0.

Note:

2 <= len(nums) <= 10000.
0 <= nums[i] < 1000000.
1 <= k <= len(nums) * (len(nums) - 1) / 2.

这道题目和378.Kth Smallest Element in a Sorted Matrix很类似，典型的值域二分问题，最小值是0，最大值是数组最大值与最小值的差，在这个值域区间内寻找。但是显然被模板套路了，这种方法会在倒数第三个大数据超时，其实稍加改动就可以通过。先看超时的解法：

class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(nullptr);

        vector<vector<int>> matrix;
        sort(nums.begin(), nums.end());
        int n = nums.size();

        for (int i = 0; i < n - 1; ++i) {
            vector<int> tmp;
            for (int j = i + 1; j < n; ++j) {
                tmp.push_back(nums[j] - nums[i]);
            }
            matrix.push_back(tmp);
        }

        int left = 0, right = nums[n - 1] - nums[0];
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            int cnt = valueBinarySearch(matrix, k, mid);
            if (cnt >= k) right = mid;
            else left = mid + 1;
        }

        return left;
    }

    int valueBinarySearch(vector<vector<int>> & matrix, int k, int target) {
        int count = 0;
        for (int i = 0; i < matrix.size(); ++i) {
            for (int j = 0; j < matrix[i].size(); ++j) {
                if (matrix[i][j] <= target) {
                    ++count;
                    continue;
                }
                break;
            }
        }

        return count;
    }
};

改动后虽然确实通过了，但是只是惊险通过。

class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(nullptr);

        sort(nums.begin(), nums.end());
        int n = nums.size();
        int left = 0, right = nums[n - 1] - nums[0];

        while (left < right) {
            int mid = left + ((right - left) >> 1);
            int cnt = 0;
            for (int i = 0; i < n - 1; ++i) {
                for (int j = i + 1; j < n; ++j) {
                    if (nums[j] - nums[i] <= mid) {
                        ++cnt;
                        continue;
                    }
                    break;
                }
            }
            if (cnt >= k) right = mid;
            else left = mid + 1;
        }

        return left;
    }
};

Runtime: 1640 ms, faster than 5.02% of C++ online submissions for Find K-th Smallest Pair Distance.
Memory Usage: 9.5 MB, less than 25.00% of C++ online submissions for Find K-th Smallest Pair Distance.

只是更换了统计方法，速度明显提升。上一种思路是从小到大比较来统计个数，这里的思路是要想办法排除掉一些没必要的计算。因为上一种我的统计思路是遍历所有的组合来统计，这里是用一个start记录上一轮寻找的左区间。很显然start和i之间的差值是每个搜寻轮次的最大差值，当左区间边界确定了，下一轮搜索时候，start左边的数就不用考虑了，因为已经有 $nums[i] - nums[start] > mid$ ，左边的数字肯定会让差值大于mid，这样就节省了很多不必要的时间。

Runtime: 16 ms, faster than 59.72% of C++ online submissions for Find K-th Smallest Pair Distance.
Memory Usage: 9.3 MB, less than 83.33% of C++ online submissions for Find K-th Smallest Pair Distance.

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[0];
        while (left < right) {
            int mid = left + (right - left) / 2, cnt = 0, start = 0;
            for (int i = 0; i < n; ++i) {
                while (start < n && nums[i] - nums[start] > mid) ++start;
                cnt += i - start;
            }
            if (cnt < k) left = mid + 1;
            else right = mid;
        }
        return right;
    }
};

时间复杂度 $O(nlogn)$ .