LeetCode中等题之找到 K 个最接近的元素

题目

给定一个 排序好 的数组 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

来源：力扣（LeetCode）

解题思路

  一个基本的思路就是直接在原数组中找到目标x的位置，然后根据x的位置向其两端发散。在例一中可以发现其实[2,3,4,5]也是符合要求的，但是结果却返回的是[1,2,3,4]，所以两端发散的顺序一定是先向左边发散，然后再看右边。根据题意如果每次发散只增长一个元素，那么需要发散k次，如果x到左边需要发散的值的距离小于等于右边的值到x的距离则可以优先发散左边(因为是小于等于)，故此题需要有两个指针left,right分别指向需要找的值或其左端，右端。

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        right=bisect.bisect(arr,x) #指向该值的右边一个位置
        left=right-1  #指向该值或者该值的左边一个位置
        for i in range(k):  #共需发散k次
            if left<0:  #如果该值或则该值的左边位置下溢
                return arr[:k]
            elif right>len(arr)-1: #如果该值的右边位置下溢
                return arr[-k:]
            elif x-arr[left]<=arr[right]-x: #向左发散
                left-=1
            else:  #向右发散
                right+=1
        return arr[left+1:right]
1
2
3
4
5
6
7
8
9
10
11
12
13
14