算法随笔_16: 找出第k小的数对距离

上一篇:算法随笔_15: 找到K个最接近的元素-CSDN博客

题目描述如下

数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。给你一个整数数组 nums 和一个整数 k ，数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length 。返回 所有数对距离中 第 k 小的数对距离。

示例 1：

输入：nums = [1,3,1], k = 1
输出：0
解释：数对和对应的距离如下：
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
距离第 1 小的数对是 (1,1) ，距离为 0 。

算法思路:

这道题有部分类似于上一篇题目。由于题目要求是找到第k小的数对距离。我们首先要考虑的就是看看能不能把数组做好排序，然后根据排序后的数组想出一些更高效的算法。

如果是暴力解法，我们需要把所有的两两组合都判断一遍，最后找出第k小的数对距离。

当我们把数组进行升序排序之后，我们会发现所有可能数对的距离最大值是数组的头尾两个元素的差，我们把这个最大的距离设为right_vle。那么，所有可能的距离值的范围就在0到right_vle之间。

我们可以先找到此距离范围的中间值mid_vle。小于mid_vle这个距离的所有数对，我们设为pairs_left。大于mid_vle这个距离的那些数对，我们设为pairs_right。

如果pairs_left的数对总个数小于k，说明第k小的数对肯定在pairs_right里。

如果pairs_left的数对总个数大于等于k，说明第k小的数对肯定在pairs_left里。

这就是典型的二分查找的情形。我们可以通过二分查找，不断的缩小区间的范围最终找到第k小的数对距离。

在实际的算法实现中我们仅仅需要设定距离区间的两个边界即可，比如:距离左边界为left_vle，距离右边界为right_vle。可以摒弃掉两个变量pairs_left，pairs_right。下面代码的第17到23行，就是这部分算法的实现。

到目前为止，我们还剩一个步骤需要去做，那就是计算left_vle到right_vle这个区间的所有数对的个数cnt。

此处，我们可以用双指针来解决这个问题。一开始两个指针都同时指向数组的开始，然后先不断的向右移动右指针，同时计算左右指针两个元素的距离

如果距离大于mid_vle，我们需要不断的移动左指针，直到距离小于mid_vle。

如果距离小于mid_vle，此时我们就可以把左右指针之间的元素个数累加到cnt。然后继续移动右指针。

下面代码的fntCnt函数就是实现的此部分算法。

class Solution(object):
    def fndCnt(self,nums,mid_vle):
        cnt=0
        i=0
        n=len(nums)
        for j in range(n):
            while nums[j] - nums[i] > mid_vle:
                i+=1
            cnt += j - i
        return cnt

    def smallestDistancePair(self,nums,k):
        nums.sort()
        left_vle=0
        right_vle=nums[len(nums)-1]-nums[0]
        
        while left_vle<=right_vle:
            mid_vle=(left_vle+right_vle)//2
            cnt=self.fndCnt(nums,mid_vle)
            if cnt< k:
                left_vle=mid_vle+1
            else:
                right_vle=mid_vle-1
        return left_vle