在未排序的數(shù)組中找到第k個(gè)最大的元素。請(qǐng)注意，你需要找的是數(shù)組排序后的第 k 個(gè)最大的元素朽基，而不是第 k 個(gè)不同的元素
示例 1:
輸入: [3,2,1,5,6,4] 和 k = 2
輸出: 5
示例 2:
輸入: [3,2,3,1,2,4,5,5,6] 和 k = 4
輸出: 4
說明:
你可以假設(shè) k 總是有效的，且 1 ≤ k ≤ 數(shù)組的長度鞋屈。
方法一：堆
思路就是創(chuàng)建一個(gè)大堆，將所有數(shù)組的元素放在堆中润绎，并保持堆中元素等于k,堆中保持前k個(gè)最大元素，這樣堆頂?shù)脑鼐褪谴鸢浮?/p>
像大小為kO(logk)火诸，我們將重復(fù)該操作 N 次，故總時(shí)間復(fù)雜度為 O(Nlog?k){O}(N \log k)O(Nlogk)。
在 Python 的 heapq 庫中有一個(gè) nlargest 方法，具有同樣的時(shí)間復(fù)雜度园细，能將代碼簡化到只有一行。
class Solution:
? ? def findKthLargest(self, nums, k):
? ? ? ? """
? ? ? ? :type nums: List[int]
? ? ? ? :type k: int
? ? ? ? :rtype: int
? ? ? ? """
? ? ? ? return heapq.nlargest(k, nums)[-1]
