題目出處
461 · Kth Smallest Numbers in Unsorted Array
難度
medium
個人範例程式碼 – 1 (相等時結束的討論)
from typing import (
List,
)
class Solution:
"""
@param k: An integer
@param nums: An integer array
@return: kth smallest element
"""
def kth_smallest(self, k: int, nums: List[int]) -> int:
# write your code here
return self.quickselect(nums, k-1, 0, len(nums)-1)
def quickselect(self, nums, k, start, end):
# recusion end
if start == end: # (==k)
return nums[k]
# recursion define
left, right = start, end
pivot = nums[(start + end) // 2]
# print(nums, pivot, start, end)
while(left <= right):
if nums[left] < pivot: # [3, 9, 4, 8]: 9 never moves.
left += 1
elif nums[right] > pivot:
right -= 1
else:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
else:
# two part start < right < left < end (<= , >)
# recursion split
if right >= k and start <= right: # search left
return self.quickselect(nums, k, start, right)
elif left <= k and left <= end: # search right
return self.quickselect(nums, k, left, end)
else:
return nums[k]
算法說明
這題用到 QuickSelect 的概念,簡單來說就是藉由「每一次都切一半,減少一半的搜尋範圍」,
分出剩餘的另外一半後,再去嘗試切一半,進行 O(logN) 的快速尋找。
這題會經常錯在遞迴判斷式與邊界條件,導致無法 AC。
遞迴判斷式
遞迴的定義
這裡我自己錯好多次,總之不熟悉處理起來很麻煩,
導入 quickselect 的概念,我們把原本要搜尋的範圍切成兩半,
將比 pivot 小的往左擺,大的往右擺,一樣大的先不管
(管了會出事,會有無限迴圈:例 [3, 9, 4, 8]: 9 never moves.)
遞迴的拆解
這邊要處理的是邊界問題,往前我們還需要多注意 while(left <= right),
這會導致我們是「交錯」才結束,
結束時的狀態為 「start < right < left < end」,由於與 pivot 相等的在兩側都有可能出現,
拆解的搜尋條件為
- start ~ right
- left ~ end
可附加條件為 「right >= k」、「left <= k」,我們可以提早結束 k 的搜尋。
- start ~ right, right >= k:左側還比 k 多,需要再排序
- left ~ end, left <= k:右側還比 k 少 (= 左側比 k 多),需要再排序
遞迴的中止
如果 start end,return nums[k] ,
怎麼保證這一定會發生就是個大問題了,這也是最常出錯的地方,我錯好多次…
簡單來說我們可以想一些比較極端的 case,程式也都要能正常結束。
例如: [1,1],k = 1 (index 0), k = 2(index 1)
這邊我暫時先這樣想,哪天有更好的想法再回來補吧。
input handling
這題沒有特別說要怎麼處理特殊的 input,預設的 input 都給正確的。
Boundary conditions
上方已經說明完囉
稍微修改一下解,修改一下定義式
這邊可以將上面的解答稍微修改一下,可能概念上會更漂亮一些。(因人而異)
主要修改的是迴圈的方式,上面的作法是「外圍跑完 N 輪,每一輪都會有決定要幹嘛」,
這邊的作法是「外圍只是限制,而每一次的 pointer 都直接迴圈到下一個要更改的點」。
概念大同小異,可以依個人決定哪個程式碼比較漂亮而決定採用哪一個。
while(left <= right):
while(left <= right and nums[left] < pivot):
left += 1
while(left <= right and nums[right] > pivot):
right -= 1
if(left <= right):
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
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 |