力扣-4题 寻找两个正序数组的中位数（C++）- 优先队列

题目链接：https://leetcode.cn/problems/median-of-two-sorted-arrays/
题目如下：

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        //用一个大根堆，一个小根堆去实现
        insert_heap(nums1,nums2);
        if(maxheap.size()==minheap.size()) return (minheap.top()+maxheap.top())/2.0;
        else return maxheap.top();
    }
    void insert_heap(vector<int>& nums1,vector<int>& nums2){
        int n1=nums1.size(),n2=nums2.size();
        int i=0,j=0;

        while(i<n1||j<n2){//将两个数组的元素分别加入优先队列中
            if(i<n1&&j<n2){
                if(nums1[i]<nums2[j]) {
                    insert(nums1[i++]);
                }else insert(nums2[j++]);
            }else if(i<n1) insert(nums1[i++]);
            else if(j<n2) insert(nums2[j++]);
        }
    }
    void insert(int num){
        //大根堆及小根堆的维护：
        //1、决定放入哪个堆 2、大小根堆的维护
        
        //step1：
        if(maxheap.size()==0||num<=maxheap.top()) maxheap.push(num);//优先考虑放大根堆，若num>堆顶元素，则堆顶元素pop
        else minheap.push(num);
        
        //step2：目的-》大顶堆元素个数==小顶堆元素个数 ，大根堆元素个数==小根堆元素个数+1
        while(maxheap.size()<minheap.size()){
            int temp=minheap.top();
            minheap.pop();
            maxheap.push(temp);
        }

        while(maxheap.size()-1>minheap.size()){
            int temp=maxheap.top();
            maxheap.pop();
            minheap.push(temp);
        }
    }
private:
    struct Cmp{
        bool operator()(const int& a,const int& b){
            return a>b;
        }
    };
    priority_queue<int> maxheap;
    priority_queue<int,vector<int>,Cmp> minheap;
};

最后

以上就是优雅冬天为你收集整理的力扣-4题 寻找两个正序数组的中位数（C++）- 优先队列的全部内容，希望文章能够帮你解决力扣-4题 寻找两个正序数组的中位数（C++）- 优先队列所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。