题目
难度：★★★☆☆
类型：数学
方法：数学
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
给定一个排序好的数组，两个整数 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解决方案，请移步力扣中等题解析
