4. 寻找两个正序数组的中位数

 1 class Solution 
 2 {
 3 public:
 4     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) 
 5     {
 6         int m = nums1.size(),n = nums2.size();
 7         int i = 0,j = 0;
 8         for(;i < m && j < n;) 
 9         {
10             if(nums1[i] < nums2[j]) addNum(nums1[i ++]);
11             else addNum(nums2[j ++]);
12         }
13         while(i < m) addNum(nums1[i ++]);
14         while(j < n) addNum(nums2[j ++]);
15 
16         if(big.size() + small.size() & 1) return small.top();
17         else return (big.top() + small.top()) / 2.0;
18     }
19 
20     priority_queue<int,vector<int>,greater<int>> small;//小根堆
21     priority_queue<int> big;//大根堆
22 public:
23     
24     void addNum(int num) //维护小根堆与大根堆相等或者比大根堆多1
25     {
26         if(big.empty() || num > big.top()) small.push(num);
27         else // big->[1],small->[2],num = 0 ——> big->[0,1],small->[2]——> big->[0],small->[1,2]
28         {
29             big.push(num);
30             small.push(big.top());
31             big.pop();
32         }
33 
34         if(small.size() > big.size() + 1)
35         {
36             big.push(small.top());
37             small.pop();
38         }
39     }
40 };