题目
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.
Can you solve it without sorting?
解题思路
方法一,维护一个大小为k的heap,把所有数字依次加入进去,堆中的最小值为最后的结果
方法二,使用quickselect
代码
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
q = []
for n in nums:
if len(q) == k:
heapq.heappushpop(q, n)
else:
heapq.heappush(q, n)
return min(q)
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
def quickSelect(nums, l, r, k):
i, j, pivot = l, r, nums[r]
while i < j:
if nums[i] > pivot:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
else:
i += 1
nums[i], nums[r] = nums[r], nums[i]
m = i - l + 1
if m == k:
return i
elif m > k:
return quickSelect(nums, l, i - 1, k)
else:
return quickSelect(nums, i + 1, r, k - m)
n = len(nums)
return nums[quickSelect(nums, 0, n - 1, n - k + 1)]
视频讲解 YouTube<--欢迎点击订阅
视频讲解 bilibili<--欢迎点击订阅
-
Previous
LeetCode 708 Insert into a Sorted Circular Linked List (Python) -
Next
LeetCode 1644 Lowest Common Ancestor of a Binary Tree II (Python)
Related Issues not found
Please contact @MaxMing0 to initialize the comment