Leetcode 658. Find K Closest Ele

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

Find K Closest Elements

2. Solution

• Version 1

class Solution:
    def findClosestElements(self, arr, k, x):
        result = []
        index = self.binarySearch(arr, x)
        left = index
        right = index + 1
        length = len(arr)
        while k:
            if left < 0:
                result = result + [arr[right]]
                right += 1
            elif right >= length:
                result = [arr[left]] + result
                left -= 1
            elif x - arr[left] <= arr[right] - x:
                result = [arr[left]] + result
                left -= 1
            else:
                result = result + [arr[right]]
                right += 1
            k -= 1
        return result


    def binarySearch(self, arr, x):
        left = 0
        right = len(arr) - 1
        index = 0
        while left <= right:
            middle = (left + right) // 2
            if arr[middle] < x:
                index = left
                left += 1
            elif arr[middle] > x:
                right -=1
                index = right
            else:
                return middle
        return index

• Version 2

class Solution:
    def findClosestElements(self, arr, k, x):
        left = 0
        right = len(arr) - k
        while left < right:
            middle = (left + right) // 2
            if x - arr[middle] >  arr[middle + k] - x:
                left = middle + 1
            else:
                right = middle
        return arr[left:left+k]

Reference

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