Leetcode 658. Find K Closest Elements

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

1. Description

Find K Closest Elements

2. Solution

  • Version 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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
1
2
3
4
5
6
7
8
9
10
11
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/
如果有收获,可以请我喝杯咖啡!