专栏首页算法码上来每日算法系列【LeetCode 658】找到 K 个最接近的元素

每日算法系列【LeetCode 658】找到 K 个最接近的元素

题目描述

给定一个排序好的数组,两个整数 k 和 x,从数组中找到最靠近 x(两数之差最小)的 k 个数。返回的结果必须要是按升序排好的。如果有两个数与 x 的差值一样,优先选择数值较小的那个数。

示例1

输入:
[1,2,3,4,5], k=4, x=3
输出:
[1,2,3,4]

示例2

输入:
[1,2,3,4,5], k=4, x=-1
输出:
[1,2,3,4]

提示

  • k 的值为正数,且总是小于给定排序数组的长度
  • 数组不为空,且长度不超过 10^4
  • 数组里的每个元素与 x 的绝对值不超过 10^4

题解

滑动窗口

这题要找离 最近的 个元素,又因为数组是排好序的,所以离 最远的元素一定在数组两端。

那么我们只需要用两个指针,一个指针 指着第一个元素,一个指针 指着最后一个元素。如果 ,那就说明窗口中元素个数大于 ,那么就要删除一个元素。删除哪个呢?就看 和 谁离 更远,就删除谁。如果一样远,就删除大的元素 。就这样删到窗口中只剩 个元素为止。

这个方法时间复杂度是 。

二分+滑动窗口

如果 太大,那么仅仅靠滑动窗口显然不行。注意观察答案所在的窗口可以发现,这个长度为 的窗口一定是靠近 的,也就是 要么在窗口前一个位置,要么在窗口后一个位置,要么在窗口中间某个位置。 和窗口中间绝对不可能有其他的数组元素。

那么我们可以二分找到第一个比 大的元素(找第一个比它小的元素也行),然后左右各伸展出 的长度,最终答案窗口一定就在这个范围之内。然后继续使用上面的滑动窗口来求解。

这个方法时间复杂度缩减到了 。

二分

如果 太大,那么上面的方法又没有意义了,还是会退化到 。

上面两个方法都是先把窗口范围定到某一个区间里,然后一点一点的缩小窗口大小,最终得到答案的。那么能否直接判断出长度为 的答案窗口位置在哪里呢?

按照上面的思路,长度为 的窗口一定是通过长度为 的窗口删除首尾之一元素得到的。那么我们观察某一个特定的长度为 的窗口 ,如果 离 距离比 离 更远的话,那就要删除 ,同时说明 以及它左边的所有元素都不可能是答案窗口的左边界。反之如果 离 距离小于等于 离 的距离,那么就要删除 了,同时说明 右边的元素都不可能是答案窗口的左边界。

综上,我们可以用二分直接寻找答案窗口的左边界。这样时间复杂度就降到了 。

代码

滑动窗口(c++)

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int n = arr.size();
        int l = 0, r = n-1;
        while (r-l >= k) {
            if (x-arr[l] <= arr[r]-x) r--;
            else l++;
        }
        vector<int> res(k);
        copy(arr.begin()+l, arr.begin()+l+k, res.begin());
        return res;
    }
};

二分+滑动窗口(c++)

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int n = arr.size();
        int l = 0, r = n-1;
        while (l < r) {
            int m = (l + r) / 2;
            if (arr[m] < x) l = m + 1;
            else r = m;
        }
        r = min(n-1, l+k-1);
        l = max(0, l-k);
        while (r-l >= k) {
            if (x-arr[l] <= arr[r]-x) r--;
            else l++;
        }
        vector<int> res(k);
        copy(arr.begin()+l, arr.begin()+l+k, res.begin());
        return res;
    }
};

二分(c++)

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int n = arr.size();
        int l = 0, r = n-k;
        while (l < r) {
            int m = (l + r) / 2;
            if (x-arr[m] > arr[m+k]-x) l = m + 1;
            else r = m;
        }
        vector<int> res(k);
        copy(arr.begin()+l, arr.begin()+l+k, res.begin());
        return res;
    }
};

滑动窗口(python)

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        n = len(arr)
        l, r = 0, n-1
        while r-l >= k:
            if x-arr[l] <= arr[r]-x:
                r -= 1
            else:
                l += 1
        return arr[l:l+k]

二分+滑动窗口(python)

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        n = len(arr)
        l, r = 0, n-1
        while l < r:
            m = (l + r) // 2
            if arr[m] < x:
                l = m + 1
            else:
                r = m
        r = min(n-1, l+k-1)
        l = max(0, l-k)
        while r-l >= k:
            if x-arr[l] <= arr[r]-x:
                r -= 1
            else:
                l += 1
        return arr[l:l+k]

二分(python)

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        n = len(arr)
        l, r = 0, n-k
        while l < r:
            m = (l + r) // 2
            if x-arr[m] > arr[m+k]-x:
                l = m + 1
            else:
                r = m
        return arr[l:l+k]

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

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

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【每日算法Day 94】经典面试题:机器人的运动范围

    地上有一个 m 行 n 列的方格,从坐标 [0, 0] 到坐标 [m-1, n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、...

    godweiyang
  • 每日算法系列【EOJ 3031】二进制倒置

    给定一个整数 、将 的 334 位二进制表示形式(不包括开头可能的值为 0 的位, 表示为 1 位 0)前后倒置,输出倒置后的二进制数对应的整数。

    godweiyang
  • 每日算法系列【LeetCode 128】最长连续序列

    我们可以遍历每个数 ,假设它是某个连续序列的开头,那么首先要满足 不在数组中,然后从 开始逐渐增大,看最大多少还在数组里。

    godweiyang
  • 给定一个数组,求子数组的最大异或和

    大学里的混子
  • C#版 - 小红书后台开发面试题: 二维数组中的查找

    在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该...

    Enjoy233
  • 生理周期POJ 1006

    Description 人生来就有三个生理周期,分别为体力、感情和智力周期,它们的周期长度为23天、28天和33天。每一个周期中有一天是高峰。在高峰这天,人会...

    attack
  • 线性同余同余方程组解法(excrt)

    【问题描述】 求关于 x 的同余方程组 x%a 1 =b 1  a1=b1 x%a 2 =b 2  a2=b2 x%a 3 =b 3  a3=b3 x%a...

    attack
  • 4.6树上的分治法(3)

    在POJ: 1741的计数函数上加个循环,只需将“不超过k”改为“不超过k减去小于k”,就可以得到“等于k”的数量了。

    用户1147447
  • ByRecyclerView:真·万能分割线 (线性/宫格/瀑布流)

    我基本上找遍了网上所有通过ItemDecoration设置分隔线的文章,但都不尽如意,它们大多只适用于部分情况,比如只能给线性布局设置、只能设置color不能设...

    Jingbin
  • java学习之二分查找法代码

    吾爱乐享

扫码关注云+社区

领取腾讯云代金券