0658. 找到 K 个最接近的元素 #

标签：数组、双指针、二分查找、排序、滑动窗口、堆（优先队列）
难度：中等

题目大意 #

给定一个有序数组 arr，以及两个整数 k、x。从数组中找到最靠近 x（两数之差最小）的 k 个数。返回包含这 k 个数的有序数组。

解题思路 #

数组的区间为 [0, n-1]，查找的子区间长度为 k。我们可以通过查找子区间左端点位置，从而确定子区间。

查找子区间左端点可以通过二分查找来降低复杂度。

因为子区间为 k，所以左端点最多取到 n-k 的位置。

设定两个指针 left，right。left 指向 0，right 指向 n-k。

每次取 left 和 right 中间位置，判断 x 与左右边界的差值。x 与左边的差值为 x - arr[mid]，x 与右边界的差值为 arr[mid + k] - x。

如果 x 与左边界的差值 > x 与右边界的差值，即 x - arr[mid] > arr[mid + k] - x，将 left 右移，left = mid + 1，从右侧继续查找。
如果 x 与左边界的差值 <= x 与右边界的差值，即 x - arr[mid] <= arr[mid + k] - x，则将 right 向左侧靠拢，right = mid，从左侧继续查找。

最后返回 arr[left, left + k] 即可。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        n = len(arr)
        left = 0
        right = n - 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]