品牌网站设计步骤企业建设网站 入账

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

解题思路

第一种是快排，快排逻辑是以一个元素作为哨兵，通过头尾指针逼近和交换元素的方法找到该哨兵的位置，此题中额外使用k进行剪枝。

第二种思路是使用堆heapify，这种方式会默认生成一个大根堆，可以通过“ListNode.__lt__ = lambda a, b: a.val < b.val # 让堆可以比较节点大小”,然后直接使用heappop返回当前最小值。

AC代码

class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:# def quicksort(nums, l, r, k):#     if l == r:#         return nums[k]#     i, j, key = l, r, nums[l]#     while i < j:#         while nums[i] < key: i += 1#         while nums[j] > key: j -= 1#         if i < j:#             nums[i], nums[j] = nums[j], nums[i]#     return quicksort(nums, l, j, k) if k <= j else quicksort(nums, i+1, r, k)# return quicksort(nums, 0, len(nums) - 1, k)heapify(nums)temp = 0for _ in range(len(nums) - k + 1):temp = heappop(nums)return temp