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

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

class FindClosestElements:
    """
    658. 找到 K 个最接近的元素
    https://leetcode.cn/problems/find-k-closest-elements/description/
    """
    def solution(self, arr: List[int], k: int, x: int) -> List[int]:
        p = self.left_bound(arr, x)

        res = []

        l, r = p - 1, p
        while r - l - 1 < k:
            if l == -1:
                res.append(arr[r])
                r += 1
            elif r == len(arr):
                res.insert(0, arr[l])
                l -= 1
            elif x - arr[l] > arr[r] - x:
                res.append(arr[r])
                r += 1
            else:
                res.insert(0, arr[l])
                l -= 1

        return res

    def left_bound(self, arr: List[int], x: int) -> int:

        l, r = 0, len(arr)
        while l < r:
            mid = l + (r - l) // 2
            if arr[mid] >= x:
                r = mid
            else:
                l = mid + 1

        return l

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39