題目出處
難度
medium
個人範例程式碼
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
start, end = 0, len(arr) - 1
while(start + 1 < end):
mid = (start + end) // 2
if arr[mid] == x:
start = mid
elif arr[mid] < x:
start = mid
else: # a[mid] > x
end = mid
else:
return self.find_k_neighbors(arr, x, k, start, end)
def find_k_neighbors(self, arr, x, k, start, end):
# print(start, end)
ans = []
while(k > 0):
if((start >= 0) and (end < len(arr)) and (x - arr[start] <= arr[end] - x)): # smaller first
ans.append(arr[start])
start -= 1
elif((start >= 0) and (end < len(arr)) and (x - arr[start] > arr[end] - x)):
ans.append(arr[end])
end += 1
elif(start < 0):
ans.append(arr[end])
end += 1
else: # end >= len(a)
ans.append(arr[start])
start -= 1
k -= 1
# print(ans)
return sorted(ans)
算法說明
方法是一樣 binary search 找到中間後 O(logN)，往兩邊搜尋 K 個 O(K)。 = O(logN+K)
個人覺得這題 LintCode 版本出的比較好，Leetcode 出的版本最後多了一個排序，
只是我覺得光是找最近的 K 的結果就已經找到的關鍵，就不用再排序了!
- LintCode 版本的題目：460 · Find K Closest Elements
Leetcode 版本的差別只差在我最後多補了一個 sorted 給他。
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
input handling
應該要做但我沒做XD，不過題目有保證輸入正確就是
Boundary conditions
binary search 的邊界條件
這裡有兩個 Boundary conditions 要注意，一個是一開始的 binary search 的邊界條件
find K 的邊界條件
另外一個要注意的是在找 K 個鄰近的數值時，我們需要注意「不能找到範圍之外」。