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] 即可。
代码 #
|
|