Skip to content

793. Find K-th Smallest Pair Distance

793. Find K-th Smallest Pair Distance

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

难度: Hard

题意:

  1. 给定一个数组
  2. 计算数组总所有点对的差
  3. 求第k大是多少

思路:

  • 暴力枚举肯定不行
  • 换种思路,我们可以二分结果,数组所有点对的差的取值范围是1到最大值-最小值
  • 二分结果,计算点对的差小于或等于这个结果有多少个,跟k比是大还是小
  • 计算点对的差小于或等于某个值p有多少个,需要遍历数组,对于每个数a,判断数组中有多少个数小于或等于a+p,累加即可
  • 复杂度是o(nlogn*logn)

解法:

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


回到顶部