首页 > itarticle > 找出第k大的数

找出第k大的数

admin 1月 28, 2021 0

题目：在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

思路：堆排序

注：可以用python中自带的堆包

class :
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        import heapq
        heapq.heapify(nums)
        return heapq.nlargest(k,nums)[-1]
        
a = Solution().findKthLargest(nums=[3,2,1,5,6,4],k=2)
print(a)

Python中heapq包中函数的用法：

import heapq          
h = []
heapq.heappush(h,10)  # 向堆中插入元素
heapq.heappop(h)      # 弹出堆顶元素
heapq.heapify(nums)   # nums为list，将nums变为堆
heapq.merge(h1,h2)    # 将两个堆进行合并