solution with min and max heap


  • 0
    Z

    '''
    struct comparator {
    bool operator()(int i, int j) {
    return i > j;
    }
    };

    class Solution {

    public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    priority_queue<int, vector<int>> small; // less-than comparison
    priority_queue<int, std::vector<int>, comparator> large;

        for (int i = 0; i<nums1.size(); i++) {
            if (small.empty()) {small.push(nums1[i]);}
            else if (nums1[i]>small.top()) {
                large.push(nums1[i]);
            } else {
                small.push(nums1[i]);
            }
        }
    
        for (int i = 0; i<nums2.size(); i++) {
            if (small.empty()) {small.push(nums2[i]);}
            else if (nums2[i]>small.top()) {
                large.push(nums2[i]);
            } else {
                small.push(nums2[i]);
            }
        }
        
        while (large.size() > (small.size() + 1)) {
            int k = large.top();
            small.push(k);
            large.pop();
        }
        
        while (small.size() > (large.size() + 1)) {
            int k = small.top();
            large.push(k);
            small.pop();
        }
        
        if (large.size()>small.size()) {return large.top();}
        else if (large.size()<small.size()) {return small.top();}
        else {return (double)(large.top() + small.top())/2.0;}
    }
    

    };
    '''


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.