動機

沒有魔法的一題

Problem

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

 

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2Output: 5

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4Output: 4

 

Constraints:

  • 1 <= k <= nums.length <= 104
  • -104 <= nums[i] <= 104

Sol

最直接的方法是排序或是heap

import heapq as hq
class Solution:
    def findKthLargest(self, nums: List[int], kkk: int) -> int:
        h = []
        for n in nums:
            hq.heappush(h,-n)
        ret = 0
        for _ in range(0,kkk):
            ret = hq.heappop(h)
        return -ret

還有quick select，但是會改list，我是不太喜歡啦