題目出處
難度
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 個鄰近的數值時,我們需要注意「不能找到範圍之外」。
Reference
⭐ Leetcode 解題紀錄 ⭐ | 題型 | 資料結構 | Python Solution | C++ Solution | Note | |
---|---|---|---|---|---|---|
⭐BFS 相關題型 ⭐ | ||||||
104 | Maximum Depth of Binary Tree | BFS (分層) | Python | |||
94 | Binary Tree Inorder Traversal | BFS (分層) | Tree | Python | 內含 處理 Tree 樹問題的重點 | |
102 | Binary Tree Level Order Traversal | BFS (分層) | Tree | Python | ||
103 | Binary Tree Zigzag Level Order Traversal | BFS (分層) | Tree | Python | ||
107 | Binary Tree Level Order Traversal II | BFS (分層) | Tree | Python | ||
133 | Clone Graph | BFS (分層) | Graph | Python | Graph 的基本操作 #重要題型 | |
127 | Word Ladder | BFS (分層), DFS | Graph | Python | ||
[Lint] 127 | Topological Sorting | BFS (拓撲) | Python | 內有 indegree, outdegree 介紹 #重要題型 | ||
207 | Course Schedule | BFS (拓樸) | Graph | Python |