侧边栏壁纸
博主头像
mkdir700博主等级

思考人生意义的码农

  • 累计撰写 31 篇文章
  • 累计创建 43 个标签
  • 累计收到 2 条评论

目 录CONTENT

文章目录

658. 找到 K 个最接近的元素

mkdir700
2022-08-25 / 0 评论 / 0 点赞 / 63 阅读 / 693 字 / 正在检测是否收录...

描述

给定一个 排序好 的数组 arr ,两个整数 k 和 x ,从数组中找到最靠近 x(两数之差最小)的 k 个数。返回的结果必须要是按升序排好的。

整数 a 比整数 b 更接近 x 需要满足:

  • |a - x| < |b - x| 或者
  • |a - x| == |b - x| 且 a < b

示例 1:

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

示例 2:

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

提示:

  • 1 <= k <= arr.length
  • 1 <= arr.length <= 104
  • arr 按 升序 排列
  • -104 <= arr[i], x <= 104

https://leetcode.cn/problems/find-k-closest-elements/


标签
#数组 #双指针 #二分查找 #堆 #排序 #逆向思维 #滑动窗口


题解

0x01 滑动窗口

一共需要找 K 个数,从 left 到 rihgt 必定一个连续的窗口,逆向思考,去掉 len(arr) - k 个数,剩下的窗口就是答案,一张图看明白:

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        n = len(arr)
        left, right = 0, n - 1
        remove = n - k
        for _ in range(remove):
            if abs(arr[left] - x) > abs(arr[right] - x):
                left += 1
            else:
                right -= 1
        return arr[left: right + 1]
0

评论区