首页 > 其他 > 详细

215. Kth Largest Element in an Array

时间:2017-05-15 11:49:22      阅读:244      评论:0      收藏:0      [点我收藏+]

 

用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

原文:http://www.cnblogs.com/lettuan/p/6855537.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!