问题描述:
给定一个 排序好
的数组 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 <= 10^4
-
arr
按 升序 排列 -10^4 <= arr[i], x <= 10^4
问题分析:
这个题目解法很多,现在咱们介绍一种最常见的方法,二分查找,然后左右扩展的方式:
(1)使用二分查找法,找到目标元素x
的插入
位置right
。
(2)确定左右最初始边界:left = right - 1
和 right
。
(3)根据 x - arr[left] 和 arr[right] - x
值的大小关系,进行左右扩展即可(左边大,就向右边扩展)。文章来源:https://www.toymoban.com/news/detail-712503.html
Python3实现:
# @Time :2023/09/13
# @Author :Liu
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int: # 找插入位置
lift, right = 0, len(nums) - 1
res = len(nums)
while lift <= right:
mid = (lift + right) // 2
if nums[mid] >= target:
right = mid - 1
res = mid
else:
lift = mid + 1
return res
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
# import bisect
# right = bisect.bisect_left(arr, x)
right = self.searchInsert(arr, x) # 插入的位置
left = right - 1
for _ in range(k): # 扩展
if left < 0:
right += 1
elif right >= len(arr) or x - arr[left] <= arr[right] - x:
left -= 1
else:
right += 1
return arr[left + 1: right]
相关参考:
[1]LeetCode:658. 找到 K 个最接近的元素
声明: 总结学习,有问题或不当之处,可以批评指正哦,谢谢。文章来源地址https://www.toymoban.com/news/detail-712503.html
到了这里,关于LeetCode:658. 找到 K 个最接近的元素 - Python的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!