658.Find_K_Closest_Elements.md

658. Find K Closest Elements

中等

https://leetcode-cn.com/problems/find-k-closest-elements/

Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.

An integer a is closer to x than an integer b if:

|a - x| < |b - x|, or
|a - x| == |b - x| and a < b

Example 1:

Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]

Example 2:

Input: arr = [1,2,3,4,5], k = 4, x = -1
Output: [1,2,3,4]

Constraints:

1 <= k <= arr.length
1 <= arr.length <= 104
arr is sorted in ascending order.
-104 <= arr[i], x <= 104

相关企业

• Facebook|19
• 谷歌 Google|4
• 亚马逊 Amazon|4
• 彭博 Bloomberg|4
• 微软 Microsoft|2

相关标签

• Array
• Two Pointers
• Binary Search
• Sorting
• Heap (Priority Queue)

相似题目

• Guess Number Higher or Lower 简单
• Guess Number Higher or Lower II 中等
• Find K-th Smallest Pair Distance 困难

BS+背向双指针 O(logn+k)

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        if not arr or len(arr) < k:
            return []

        right = self.findUpperClosestElement(arr, x)
        left = right - 1

        result = []
        for _ in range(k):
            if self.isLeftCloser(arr, left, right, x):
                result.append(arr[left])
                left -= 1
            else: 
                result.append(arr[right])
                right += 1
        return sorted(result)


    def findUpperClosestElement(self, arr, target):
        start, end = 0, len(arr)-1

        while start + 1 < end:
            mid = start + (end - start) // 2
            if arr[mid] > target:
                end = mid
            elif arr[mid] == target:
                end = mid
            elif arr[mid] < target:
                start = mid

        if arr[start] >= target:
            return start
        if arr[end] >= target:
            return end
        return len(arr) # if not found then k closeest is k largest

    def isLeftCloser(self, arr, left, right, target):
        if left < 0:
            return False
        if right >= len(arr):
            return True
        if abs(arr[left] - target) <= abs(arr[right] - target): # left < right is known
            return True
        return False