Leetcode 215. Kth Largest Element in an Array

Given an integer array nums and an integer k, return the k^th largest element in the array.

Note that it is the k^th largest element in the sorted order, not the k^th 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();
    }
};

Python

C++

相關