我想做一个网站 不知道找谁做,做的不好的网站,南阳网站运营招聘信息,北京有名的设计公司给定整数数组 nums 和整数 k#xff0c;请返回数组中第 k 个最大的元素。 请注意#xff0c;你需要找的是数组排序后的第 k 个最大的元素#xff0c;而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 解题思路
第一种是快排#xff0c;快… 给定整数数组 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, i1, 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
