Leetcode 658. Find K Closest Elements

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

1. Description

2. Solution

• Version 1

代码语言：javascript复制

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

代码语言：javascript复制

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/

sdn com version 博客

0 人点赞