LWC 56：719. Find K-th Smallest Pair Distance

用户1147447

发布于 2018-01-02 10:56:57

5760

发布于 2018-01-02 10:56:57

文章被收录于专栏：机器学习入门

LWC 56：719. Find K-th Smallest Pair Distance

传送门：719. Find K-th Smallest Pair Distance

Problem:

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.

思路：排序+二分+尺取法，实际上对数组排序后，小于某个数的对数可以在线性时间内求出（尺取法的思想），那么意味着问题需要猜值验证，所以二分，代码如下：

    public int smallestDistancePair(int[] nums, int k) {
        int n = nums.length;
        Arrays.sort(nums);
        int lf = -1;
        int rt = nums[n - 1] - nums[0];

        while (rt - lf > 1) {
            int mid = lf + (rt - lf) / 2;
            if (count(nums, mid) < k) {
                lf = mid;
            }
            else {
                rt = mid;
            }
        }
        return rt;
    }

    public int count(int[] nums, int mid) {  // <= mid 的个数
        int n = nums.length;
        int cnt = 0;

        int j = 0;

        for (int i = 1; i < n; ++i) {
            while (j < i && nums[i] - nums[j] > mid) j++;
            cnt += i - j;
        }

        return cnt;
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017-10-29 ，如有侵权请联系 cloudcommunity@tencent.com 删除

absolute