題目出處
難度
medium
個人範例程式碼 - 1 (相等時結束的討論)
from typing import (
List,
)
class Solution:
"""
@param nums: The integer array you should partition
@param k: An integer
@return: The index after partition
"""
def partition_array(self, nums: List[int], k: int) -> int:
# write your code here
if not nums:
return 0
start, end = 0, len(nums)-1
while(start < end):
if nums[start] < k:
start += 1
elif nums[end] >= k:
end -= 1
else:
nums[start], nums[end] = nums[end], nums[start]
start += 1
end -= 1
else:
# the first index i nums[i] >= k
if nums[start] >= k:
return start
elif nums[end] >= k:
return end
else:
return end+1 # special case, all < k
算法說明
基本的 partition 作法，#重要題型
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
input handling
處理 input 為 [] 的情況，輸出 0
Boundary conditions
注意結束條件，start < end ，表示當 「start end」 會結束。
特殊情況：全部 < k
這時候依照題目敘述，我們應該要回傳 end + 1，
但 end + 1，不會在我們的搜尋範圍，因此「我們需要特別做討論」。
個人範例程式碼 - 2 (start 超過 end 時才結束的討論)
from typing import (
List,
)
class Solution:
"""
@param nums: The integer array you should partition
@param k: An integer
@return: The index after partition
"""
def partition_array(self, nums: List[int], k: int) -> int:
# write your code here
if not nums:
return 0
start, end = 0, len(nums)-1
while(start <= end):
if nums[start] < k:
start += 1
elif nums[end] >= k:
end -= 1
else:
nums[start], nums[end] = nums[end], nums[start]
start += 1
end -= 1
else:
return start
算法說明
基本的 partition 作法，#重要題型
這裡展示另外一種作法，是為了處理 end + 1 搜尋
透過改變條件「start <= end」，因此只有當 start 與 end 交錯時才會終止。
當全部 < k 時，start 會走到 end + 1 並結束。
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
input handling
處理 input 為 [] 的情況，輸出 0
Boundary conditions
注意結束條件，start <= end ，表示當 start 與 end 相交會結束。
特殊情況：全部 < k
在這個 case 當中，我們改變了條件「start <= end」，
因此如果全部都 < k 的情況 start 會走到 end + 1，得到最終結果。