# Leetcode|Find K Closest Elements

01

Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

Input: [1,2,3,4,5], k=4, x=3 Output: [1,2,3,4]

Input: [1,2,3,4,5], k=4, x=-1Output: [1,2,3,4]

Note: The value k is positive and will always be smaller than the length of the sorted array. Length of the given array is positive and will not exceed 104 Absolute value of elements in the array and x will not exceed 104

02

1. x 小于等于 arr[0]
2. x 大于等于 arr[-1]

1. 距离等于0的元素个数大于或等于k
2. 距离等于0的元素个数小于k，这种情况求解，稍微复杂，需要二分动态查找。

03

python代码

```"""
arr: array wanted to search
k : k numbers nearest to x
x: goal center point
assert:
1. arr is sorted
2. ele in arr is integer
"""
def findKNearestToX(arr=[1,3,5],k=2,x=0):
# x less or equal than arr[0]
if x <= arr[0]:
return arr[:k]
# x bigger or equal than arr[-1]
if x >= arr[-1]:
return arr[-k:]
# ordinary cases: at least one zero,
# distance distribution: decline-->0-->rise
hi=0
zerolen=0
for i,item in enumerate(arr):
item = abs(item-x)
if item==0:
hi=i
zerolen+=1
if zerolen == k:
return arr[hi-zerolen+1:hi+1]
# here shows: number of zero chunk is less than k
# then it needs to dynamic binary search
lo = hi - zerolen+1
curlen = zerolen
while curlen < k:
if lo > 0 and abs(arr[lo-1]-x) <= abs(arr[hi+1]-x):
lo-=1
elif hi < len(arr):
hi+=1
curlen+=1
return arr[lo:hi+1]```
```#单元test
#1
kNearest = findKNearestToX(arr=[1,3,5],k=2,x=0)
#2
kNearest = findKNearestToX(arr=[1,3,5],k=2,x=5)
#3
#3-1
kNearest = findKNearestToX(arr=[1,3,3,3,5],k=2,x=3)
#3-2
kNearest = findKNearestToX(arr=[1,3,4,5],k=3,x=3)
#3-3
kNearest = findKNearestToX(arr=[-1,3,4,4],k=3,x=3)
print(kNearest)```

298 篇文章90 人订阅

0 条评论

## 相关文章

3827

2965

2948

4148

### 【Leetcode】81. 搜索旋转排序数组 II

( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

1572

2136

1264

1395

1393

### Python高级数组处理模块numpy用法精要

numpy是Python的高级数组处理扩展库，提供了Python中没有的数组对象，支持N维数组运算、处理大型矩阵、成熟的广播函数库、矢量运算、线性代数、傅里叶变...

4047