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.
You must solve it in O(n)
time complexity.
Kth Largest Element in an Array :
給定一個整數數組 nums 和一個整數 k,返回數組中第 k 個最大的元素。
必須在 O(n) 時間複雜度內
Python
方法一 :
將nums排列之後,取倒數第k個值即為答案
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
nums.sort() #排序
return nums[-k] #倒數第k個值
方法二 : heapq模組
heap是一種特殊的二元樹,從上到下,左到右都是填滿的二元樹,且父節點值永遠小於子節點(越上面越小)
把amount限制在大於k,並pop出多餘的最小元素(heappop)
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
heapq.heapify(nums)
amount = len(nums)
while amount > k:
heapq.heappop(nums)
amount -= 1
return nums[0]
C++
維護一個最小堆,堆的大小為k,當堆的大小小於k時,我們將元素加入堆中;當堆的大小等於k時,我們將元素與堆頂元素進行比較。如果當前元素比堆頂元素大,則將堆頂元素彈出,將當前元素加入堆中。最後堆中剩餘的元素就是數組中前k大的元素。
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> minHeap;
for (int num : nums) {
if (minHeap.size() < k) {
minHeap.push(num);
} else if (num > minHeap.top()) {
minHeap.pop();
minHeap.push(num);
}
}
return minHeap.top();
}
};