題目出處

31 · Partition Array

難度

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，得到最終結果。

Reference

• 数组划分 · Partition Array