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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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;
};