LeetCode Hot 100：堆

LeetCode Hot 100：堆

215. 数组中的第K个最大元素

思路 1：优先队列

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq;
        for (int& num : nums)
            pq.push(num);
        for (int i = 0; i < k - 1; i++)
            pq.pop();
        return pq.top();
    }
};

思路 2：排序

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        if (k > nums.size())
            return -1;

        sort(nums.begin(), nums.end(), greater<int>());
        return nums[k - 1];
    }
};

347. 前 K 个高频元素

思路 1：哈希表 + 优先队列

class Solution {
private:
    class comp {
    public:
        bool operator()(const pair<int, int>& p1, const pair<int, int>& p2) {
            return p1.second > p2.second;
        }
    };

public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> hashMap;
        for (int i = 0; i < nums.size(); i++)
            hashMap[nums[i]]++;

        priority_queue<pair<int, int>, vector<pair<int, int>>, comp> pq;
        for (auto &p : hashMap) {
            pq.push(p);
            if (pq.size() > k)
                pq.pop();
        }

        vector<int> ans(k);
        for (int i = 0; i < k; i++) {
            ans[i] = pq.top().first;
            pq.pop();
        }
        return ans;
    }
};

295. 数据流的中位数

思路 1：有序集合 + 双指针

class MedianFinder
{
private:
    multiset<int> nums;
    multiset<int>::iterator left, right;

public:
    MedianFinder() : left(nums.end()), right(nums.end()) {}

    void addNum(int num)
    {
        const size_t n = nums.size();

        nums.insert(num);
        if (n == 0)
        {
            left = right = nums.begin();
        }
        else if (n % 2 == 1)
        {
            if (num < *left)
                left--;
            else
                right++;
        }
        else
        {
            if (num > *left && num < *right)
            {
                left++;
                right--;
            }
            else if (num >= *right)
                left++;
            else
            {
                right--;
                left = right;
            }
        }
    }

    double findMedian()
    {
        return (*left + *right) / 2.0;
    }
};

思路 2：对顶堆

class MedianFinder {
private:
    // 大顶堆，top 是其最大的元素，存储小于等于中位数的数
    priority_queue<int, vector<int>, less<int>> maxHeap;
    // 小顶堆，top 是其最小的元素，存储大于中位数的数
    priority_queue<int, vector<int>, greater<int>> minHeap;

public:
    MedianFinder() {}

    void addNum(int num) {
        maxHeap.push(num);
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        }
        while (!minHeap.empty() && maxHeap.top() > minHeap.top()) {
            int x = maxHeap.top(), y = minHeap.top();
            maxHeap.pop();
            maxHeap.push(y);
            minHeap.pop();
            minHeap.push(x);
        }
    }

    double findMedian() {
        double res;
        if ((maxHeap.size() + minHeap.size()) % 2 == 1)
            res = (double)maxHeap.top();
        else
            res = (maxHeap.top() + minHeap.top()) / 2.0;

        return res;
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */