Leetcode 658. Find K Closest Elements

Tyan

发布于 2021-03-02 16:28:11

36500

代码可运行

文章被收录于专栏：SnailTyanSnailTyan

运行总次数：0

代码可运行

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

1. Description

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]