658. 找到 K 个最接近的元素
499
2022-08-25
描述
给定一个 排序好 的数组 arr
,两个整数 k
和 x
,从数组中找到最靠近 x
(两数之差最小)的 k
个数。返回的结果必须要是按升序排好的。
整数 a
比整数 b
更接近 x
需要满足:
|a - x| < |b - x|
或者|a - x| == |b - x|
且a < b
示例 1:
**输入:**arr = [1,2,3,4,5], k = 4, x = 3
输出:[1,2,3,4]
示例 2:
**输入:**arr = [1,2,3,4,5], k = 4, x = -1
输出:[1,2,3,4]
提示:
1 <= k <= arr.length
1 <= arr.length <= 104
arr
按 升序 排列-104 <= arr[i], x <= 104
https://leetcode.cn/problems/find-k-closest-elements/
标签
#数组 #双指针 #二分查找 #堆 #排序 #逆向思维 #滑动窗口
题解
0x01 滑动窗口
一共需要找 K 个数,从 left 到 rihgt 必定一个连续的窗口,逆向思考,去掉 len(arr) - k
个数,剩下的窗口就是答案,一张图看明白:
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
n = len(arr)
left, right = 0, n - 1
remove = n - k
for _ in range(remove):
if abs(arr[left] - x) > abs(arr[right] - x):
left += 1
else:
right -= 1
return arr[left: right + 1]
- 0
- 0
-
分享