項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 search-input 尚未註冊或是沒有一個 view.php 檔案.

【Leetcode】python – [658] Find K Closest Elements 個人解法筆記

題目出處

658. Find K Closest Elements

難度

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 的結果就已經找到的關鍵,就不用再排序了!

Leetcode 版本的差別只差在我最後多補了一個 sorted 給他。

最近在練習程式碼本身就可以自解釋的 Coding style,可以嘗試直接閱讀程式碼理解

input handling

應該要做但我沒做XD,不過題目有保證輸入正確就是

Boundary conditions

binary search 的邊界條件

這裡有兩個 Boundary conditions 要注意,一個是一開始的 binary search 的邊界條件

find K 的邊界條件

另外一個要注意的是在找 K 個鄰近的數值時,我們需要注意「不能找到範圍之外」。

Reference

⭐ Leetcode 解題紀錄 ⭐題型資料結構Python SolutionC++ SolutionNote
⭐BFS 相關題型 ⭐
104Maximum Depth of Binary TreeBFS (分層)Python
94Binary Tree Inorder TraversalBFS (分層)TreePython 內含 處理 Tree 樹問題的重點
102Binary Tree Level Order TraversalBFS (分層)TreePython
103Binary Tree Zigzag Level Order TraversalBFS (分層)TreePython
107Binary Tree Level Order Traversal IIBFS (分層)TreePython
133Clone GraphBFS (分層)GraphPython Graph 的基本操作 #重要題型
127Word LadderBFS (分層), DFSGraphPython
[Lint] 127Topological SortingBFS (拓撲)Python
內有 indegree, outdegree 介紹 #重要題型
207Course ScheduleBFS (拓樸)GraphPython