Leetcode 658. Find K Closest Elements

文章作者：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 = indexright = index + 1length = len(arr)while k:if left < 0:result = result + [arr[right]]right += 1elif right >= length:result = [arr[left]] + resultleft -= 1elif x - arr[left] <= arr[right] - x:result = [arr[left]] + resultleft -= 1else:result = result + [arr[right]]right += 1k -= 1return resultdef binarySearch(self, arr, x):left = 0right = len(arr) - 1index = 0while left <= right:middle = (left + right) // 2if arr[middle] < x:index = leftleft += 1elif arr[middle] > x:right -=1index = rightelse:return middlereturn index

• Version 2

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

Reference

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