題目出處

5 · Kth Largest Element

難度

medium

個人範例程式碼

from typing import (
    List,
)

class Solution:
    """
    @param k: An integer
    @param nums: An array
    @return: the Kth largest element
    """
    def kth_largest_element(self, k: int, nums: List[int]) -> int:
        # write your code here
        if not nums:
            return -1 # not found

        # 1, 2, 3,  first: idx = 2 = len(s)-k (k=1)
        return self.quickselect(k-1, nums, 0, len(nums)-1)

    def quickselect(self, k, nums, start, end):
        if not nums:
            return -1

        # recursion end
        if start == end:
            return nums[k]

        # recursion define
        left, right = start, end
        pivot = nums[(start + end) // 2]
        while(left <= right):
            while(left <= right and nums[left] > pivot): # bigger go to left, descending sorting
                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
        else: # recursion split # start < right < left < end
            # print(nums)
            if start <= right and right >= k: # search left and still need sorting
                return self.quickselect(k, nums, start, right)
            elif left <= end and left <= k: # search right and still need sorting
                return self.quickselect(k, nums, left, end)
            else:
                return nums[k]

算法說明

• 此題有類似題，可參考：

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

最大的差別只在於 smallest 變 largest，簡單處理把 ascending 換成 descending 即可。

這題用到 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

上方已經說明完囉

Reference

• 无序数组K小元素 · Kth Smallest Numbers in Unsorted Array