题目

难度：★★★☆☆
类型：数学
方法：数学

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给定一个排序好的数组，两个整数 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 的值为正数，且总是小于给定排序数组的长度。
数组不为空，且长度不超过 104
数组里的每个元素与 x 的绝对值不超过 104

解答

解法1：滑动窗口

题目的要求是，在arr排序数组中，找到k个与x最接近的数字，并按顺序返回。

我们准备一个长度为k的窗口，在arr数组上滑动的过程中，该窗口中的元素一定会存在某种情况，成为题目的答案，重要的是，如何控制窗口的停止滑动。

窗口停止滑动时，应该满足的是，窗口最右端的元素与x的绝对值差值不大于窗口最左端的元素。

class Solution:
    def findClosestElements(self, arr, k: int, x: int):
        heap = []
        for i in range(len(arr)):
            if len(heap) < k:
                heap.append(arr[i])
            else:
                if abs(arr[i] - x) < abs(heap[0] - x):
                    heap.pop(0)
                    heap.append(arr[i])
        return heap

解法2：二分法

处理已经排序好的数组的最高效的方法是二分法。二分法有几个关键因素，即左右起始端点的确定，状态的更新以及返回的结果。我们这里使用二分法的目标是，找到中点mid，作为最终返回的窗口的左端位置。

左右端点的确定：选取左端点位置为0，右端点位置为len(arr)-k，因为mid作为左端，一定不会超过这个值。

状态更新：x - arr[mid] > arr[mid + k] - x时，左端点右移，否则右端点左移。

class Solution:
    def findClosestElements(self, arr, k: int, x: int):
        size = len(arr)
        left = 0
        right = size - k
        while left < right:
            mid = left + (right - left) // 2
            if x - arr[mid] > arr[mid + k] - x:
                left = mid + 1
            else:
                right = mid
        return arr[left:left + k]

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析