題目說明

給定一個陣列 nums，回傳第 k 大的數值

解題思路

這題可以透過內建函式 sort 迎刃而解，然而其實會用到 quickSort 的概念

• Time Complexity: O(nlog)
• Space Complexity:

程式碼

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        self.quickSort(nums, 0, len(nums) - 1)
        return nums[len(nums) - k]

    def quickSort(self, nums: List[int], start:int, end:int) -> int:
        if start < end:
            pivot = self.partition(nums, start, end)  
            self.quickSort(nums, start, pivot - 1)  
            self.quickSort(nums, pivot + 1, end)  

    def partition(self, nums: List[int], start:int, end:int) -> int:

        pivot = end  
        pivotIndex = start  

       
        for i in range(start, end):
           
            if nums[i] < nums[pivot]:
                self.swap(nums, i, pivotIndex)  
                pivotIndex += 1
        self.swap(nums, pivot, pivotIndex)  
        return pivotIndex


    def swap(self, nums: List[int], i:int, j:int) -> int:
        temp = nums[i]
        nums[i] = nums[j]
        nums[j] = temp

其他討論

也可以透過 heap 解這題

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        h = [-n for n in nums]
        heapq.heapify(h)
        for i in range(k-1):
            heapq.heappop(h)
        return -heapq.heappop(h)