[LeetCode]Find K Closest Elements

题目描述:

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 104
  3. Absolute value of elements in the array and x will not exceed 104

题目大意:

给定一个排序数组,两个整数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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

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