描述

给定一个 排序好 的数组 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]