LeetCode: 658. 找到 K 个最接近的元素¶
1、题目描述¶
给定一个排序好的数组,两个整数 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
更新(2017/9/19): 这个参数 arr 已经被改变为一个整数数组(而不是整数列表)。 请重新加载代码定义以获取最新更改。
2、解题思路¶
- 找到x对应的位置(左面的小于x),然后从这个点开始向两边扩展
from typing import List import bisect class Solution: def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]: right = bisect.bisect(arr, x) left = right - 1 while k > 0: if left < 0: right += k break if right >= len(arr): left -= k break if x - arr[left] <= arr[right] - x: left -= 1 else: right += 1 k -= 1 return arr[left + 1:right]