题目描述：

LeetCode 658. Find K Closest Elements

Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

Example 1:

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

Example 2:

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

Note:

1. The value k is positive and will always be smaller than the length of the sorted array.
2. Length of the given array is positive and will not exceed 10⁴
3. Absolute value of elements in the array and x will not exceed 10⁴

题目大意：

给定一个排序数组，两个整数k和x，求数组中距离x最近的k个数字。结果应该有序，距离相同时优先选择较小的数字。

解题思路：

二分查找（Binary Search）

利用二分查找，在arr中找到不大于x的最大值下标，记为lo，令hi = lo + 1；

lo和hi分别标识候选数字的左右边界

利用线性探测拓展lo和hi

Python代码：

class Solution(object):
    def findClosestElements(self, arr, k, x):
        """
        :type arr: List[int]
        :type k: int
        :type x: int
        :rtype: List[int]
        """
        size = len(arr)
        lo = max(bisect.bisect_right(arr, x) - 1, 0)
        hi = lo + 1
        left = right = lo
        cnt = 0
        while cnt < k and (lo >= 0 or hi < size):
            cnt += 1
            if hi >= size or lo >= 0 and x - arr[lo] <= arr[hi] - x:
                left = lo
                lo -= 1
            else:
                right = hi
                hi += 1
        return arr[left : right + 1]

 

本文链接：http://bookshadow.com/weblog/2017/08/13/leetcode-find-k-closest-elements/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码