首页 > 代码库 > 215. Kth Largest Element in an Array
215. Kth Largest Element in an Array
用heap解,
方法1. 维护一个 size = k 的最小堆。当前元如果大于堆顶的元素,那么说明堆顶的元素肯定小于kth largest element。所以replace他。
1 class Solution(object): 2 def findKthLargest(self, nums, k): 3 """ 4 :type nums: List[int] 5 :type k: int 6 :rtype: int 7 """ 8 heap = [] 9 res = 0 10 11 for i in range(len(nums)): 12 if i < k: 13 heapq.heappush(heap, nums[i]) 14 else: 15 if heap[0] < nums[i]: 16 heapq.heapreplace(heap, nums[i]) 17 18 19 return heap[0]
或者维护一个-nums的最小堆,从heap pop出第k个元素。那么这个数就是 -nums的第k小元素,也就是nums的第k大元素。
class Solution(object): def findKthLargest(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ heap = [] res = 0 for i in range(len(nums)): heapq.heappush(heap, -nums[i]) for j in range(k): res = -heapq.heappop(heap) return res
215. Kth Largest Element in an Array
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。