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

Difficulty
Medium
Tags
二分查找
URL
https://leetcode-cn.com/problems/find-k-closest-elements/
Star
给定一个排序好的数组 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
  • 数组里的每个元素与 x 的绝对值不超过 104

二分查找

思路
用二分法来找左边界。
左边界的范围是[0, len(arr)-k] 是左右均闭的区间。
notion imagenotion image
搜索区间是左右均闭合的
但是每次比较的时候 是nums[idx] 和 nums[idx+k]做比较，注意此处的 nums[idx+k]已经不在当前的这k个数字内了，属于是和后一组做对比了。有点类似 山脉数组中 nums[m] 和nums[m+1]做对比。所以此时 r = m，而不是 r=m-1
题解
class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        left, right = 0, len(arr) - k
        while left < right:
            mid = left + (right - left) // 2
            if x - arr[mid] <= arr[mid+k] - x:
                right = mid
            else:
                left = mid + 1

        return arr[left:left+k]
思路2
先找到小于等于 target 的最大的数字，然后以此为中心，向周围扩散k次，拿到k个数字
题解 
class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        if len(arr) == k:
            return arr
        # 思路：先找到小于等于x的最大的数字，然后从这里开始扩散k个值
        # 1. 找小于等于x的最大的数字 
        left, right = 0, len(arr)-1
        while left <= right:
            mid = left + (right-left) // 2
            if arr[mid] <= x:
                left = mid + 1
            else:
                right = mid - 1

        if right == -1:
            return arr[0:k]

        # 2. 从right 开始扩散 选择k个数字
        # 最后的结果是不包含 num[left] 和nums[right] 的
        # 而是 left right 中间包括的k个数字，所以下面需要扩散k次。
				# 初始的时候 left，right中间没有任何数字
        left, right = right, right+1 
        for _ in range(k):
            if right >= len(arr) or (left >= 0 and x - arr[left] <= arr[right] - x):
                left -= 1
            else: 
                right += 1

        return arr[left+1: right]