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

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]
本站总访问量  次  |  您是本站第  位访问者