题目描述：

LeetCode 719. 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:

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

题目大意：

给定整数数组nums表示x轴上的点，求两点间第k小距离的值

解题思路：

二分枚举答案（Binary Search）

利用字典cnt统计各点坐标及其出现次数

排序后将坐标保存在数组keys中，vals中保存对应出现次数的累计值

距离最小值lo可以通过遍历keys得出，距离最大值hi为keys[-1] - keys[0]

在lo ~ hi之间二分枚举距离mi，利用O(n)的遍历统计距离不大于mi的点对个数

Python代码：

class Solution(object):
    def smallestDistancePair(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        cnt = collections.Counter(nums)
        keys, vals = [], []
        for key in sorted(cnt):
            keys.append(key)
            vals.append(cnt[key] + (vals and vals[-1] or 0))

        def countNums(val):
            idx = bisect.bisect_right(keys, val)
            if idx: return vals[idx - 1]
            return 0

        def smallerThan(val):
            ans = 0
            for i, key in enumerate(keys):
                ans += (countNums(key + val) - vals[i]) * cnt[key] + cnt[key] * (cnt[key] - 1) / 2
            return ans

        lo = min(keys[x + 1] - keys[x] for x in range(len(keys) - 1)) \
                if max(cnt.values()) == 1 else 0
        hi = keys[-1] - keys[0]

        while lo <= hi:
            mi = (lo + hi) / 2
            if smallerThan(mi) >= k: hi = mi - 1
            else: lo = mi + 1
        return lo

 

本文链接：http://bookshadow.com/weblog/2017/10/29/leetcode-find-k-th-smallest-pair-distance/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码