215 - Kth Largest Element in an Array

解法一 - Min Heap

這題應該算是 min heap 的基本應用題,直接上 code:

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> minHeap;

        for(auto& n: nums) {
            minHeap.push(n);

            if(minHeap.size() > k) {
                minHeap.pop();
            }
        }

        return minHeap.top();
    }
};

解法二 - Sort

我們也可以先 sort 完,再拿第 k 大的 element:

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        return nums[nums.size()-k];
    }
};

results matching ""

    No results matching ""