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

【Lintcode】python – [461] Kth Smallest Numbers in Unsorted Array 個人解法筆記 #重要題型 #常錯題型

題目出處

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 SolutionC++ SolutionNote
⭐BFS 相關題型 ⭐
104Maximum Depth of Binary TreeBFS (分層)Python
94Binary Tree Inorder TraversalBFS (分層)TreePython 內含 處理 Tree 樹問題的重點
102Binary Tree Level Order TraversalBFS (分層)TreePython
103