专栏首页算法码上来每日算法系列【LeetCode 719】找出第 k 小的距离对

每日算法系列【LeetCode 719】找出第 k 小的距离对

题目描述

给定一个整数数组,返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。

示例1

输入:
nums = [1,3,1]
k = 1
输出:
0
解释:
所有数对如下:
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
因此第 1 个最小距离的数对是 (1,1),它们之间的距离为 0。

提示

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

题解

注意到这题 比较大,所以不能算出所有的数对差值,然后排序,这样时间复杂度就是 了。

直觉上应该先给数组从小到大排个序,那么差值最小值就是 0 ,最大值就是 ,答案肯定也就在这个区间里了。

那么我们可以从最大的差值开始,看是否有数对满足这个差值,并且这个差值还得是第 小的。对于差值 ,如果它是第 小的,说明所有数对中差值小于等于 的数对个数 一定大于等于 。因为如果第 小的差值只有一个数对满足,那么 ,否则的话就有多个数对差值都是 ,那就有 。于是我们找到第一个满足 的差值就行了,再加 1 就是最终的答案。

那么怎么求小于等于 的数对个数 呢?因为排过序了,所以可以采用双指针的方法,初始时 ,对于每个右指针 ,我们移动左指针 ,直到 。那么最终 就是以 作为较大数的数对个数。因为两个指针都是向右移动的,所以每次计算个数只需要 的时间复杂度。

所以这个方法最终总的时间复杂度为 ,因为最大差值 还是太大,所以还是没有办法直接遍历。

又注意到随着 的减小, 也是单调减小的,所以可以二分寻找 。如果 ,那么说明答案小于等于 ,于是令 。如果 ,那么说明答案一定大于 ,于是令 ,最终答案就是 。

这样二分优化之后,最终的时间复杂度为 ,可以接受。

代码

c++

class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int l = 0, r = nums[n-1]-nums[0];
        while (l < r) {
            int m = (l + r) / 2;
            if (count(m, nums) >= k) r = m;
            else l = m + 1;
        }
        return l;
    }

    int count(int K, vector<int>& nums) {
        int cnt = 0, l = 0, n = nums.size();
        for (int r = 0; r < n; ++r) {
            while (l < r && nums[r]-nums[l] > K) {
                l++;
            }
            cnt += r - l;
        }
        return cnt;
    }
};

python

class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        n = len(nums)
        nums.sort()

        def count(K: int) -> int:
            cnt, l = 0, 0
            for r in range(n):
                while l < r and nums[r]-nums[l] > K:
                    l += 1
                cnt += r - l
            return cnt

        l, r = 0, nums[-1]-nums[0]
        while l < r:
            m = (l + r) // 2
            if count(m) >= k:
                r = m
            else:
                l = m + 1
        return l

作者简介:godweiyang知乎同名华东师范大学计算机系硕士在读,方向自然语言处理与深度学习。喜欢与人分享技术与知识,期待与你的进一步交流~

本文分享自微信公众号 - 算法码上来(GodNLP),作者:godweiyang

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 每日算法系列【LeetCode 1250】检查「好数组」

    给你一个正整数数组 nums ,你需要从中任选一些子集,然后将子集中每一个数乘以一个任意整数,并求出他们的和。

    godweiyang
  • 每日算法系列【LeetCode 153】寻找旋转排序数组中的最小值

    (例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2])。

    godweiyang
  • 【每日算法Day 75】字节跳动面试题:手撕困难题,看过我Day 71的人都会做了!

    韦阳的博客:【每日算法Day 71】面试官想考我这道位运算题,结果我给出了三种解法[2]

    godweiyang
  • 每日算法系列【LeetCode 1250】检查「好数组」

    给你一个正整数数组 nums ,你需要从中任选一些子集,然后将子集中每一个数乘以一个任意整数,并求出他们的和。

    godweiyang
  • Leetcode 456. 132 Pattern

    Tyan
  • leetcode-easy-array-两数之和

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

    shengjk1
  • Leetcode 41. First Missing Positive

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • 【每日一题】41. First Missing Positive

    Given an unsorted integer array, find the smallest missing positive integer.

    公众号-不为谁写的歌
  • Array - 219. Contains Duplicate II

    Given an array of integers and an integer k, find out whether there are two dist...

    用户5705150
  • LeetCode | 1.两数之和

    上面的题就是 两数之和 题目的截图,同时 LeetCode 会根据选择的语言给出了一个类的定义或者函数的定义,然后在其中实现 两数之和 的解题过...

    码农UP2U

扫码关注云+社区

领取腾讯云代金券