readable c++ solution


  • -1

    This solution was inspired by this post, and is not optimized so corner cases are dealt explicitly. Hope that makes it easier to grasp the idea.

    class Solution {
    public:
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
            // insert a number if size of a vector is odd, record the added number
            pair<bool,int> addedNum1;
            pair<bool,int> addedNum2;
            
            if (nums1.size() % 2 == 1) {
                nums1.insert(nums1.begin() + nums1.size()/2, nums1[nums1.size()/2]);
                addedNum1.first = true;
                addedNum1.second = nums1[nums1.size() / 2];
            }
            
            if (nums2.size() % 2 == 1) {
                nums2.insert(nums2.begin() + nums2.size()/2, nums2[nums2.size()/2]);
                addedNum2.first = true;
                addedNum2.second = nums2[nums2.size() / 2];
            }
        
            int cut1 = nums1.size() / 2;
            int cut2 = nums2.size() / 2;
        
            // move the cuts, numbers on the left sides of the cuts should be less than or equal to those on the right sides
            while (cut1 < nums1.size() && cut2 > 0 && nums1[cut1] < nums2[cut2-1]) {
                cut1++;
                cut2--;
            }
            
            while (cut2 < nums2.size() && cut1 > 0 && nums2[cut2] < nums1[cut1-1]) {
                cut1--;
                cut2++;
            }
        
            // take the median of two numbers: the larger number of the left and the smaller number of the right
            // take care of cases where cuts are on the edge
            int left1, left2;
            left1 = cut1 == 0 ? nums2[cut2-1] : nums1[cut1-1];
            left2 = cut2 == 0 ? nums1[cut1-1] : nums2[cut2-1];
            int left = max(left1, left2);
        
            int right1, right2;
            right1 = cut1 == nums1.size() ? nums2[cut2] : nums1[cut1];
            right2 = cut2 == nums2.size() ? nums1[cut1] : nums2[cut2];
            int right = min(right1, right2);
        
            double median;
            // if the sum of sizes was odd, then we added exactly one extra number. If the extra is on the left
            // side of the cut, the median is the min of the right, vice versa
            if (addedNum1.first && !addedNum2.first)
                median = addedNum1.second <= left ? right : left;
            else if (!addedNum1.first && addedNum2.first)
                median = addedNum2.second <= left ? right : left;
            else
                median = (left + right) / 2.0;
                
            return median;
        }
    };
    

Log in to reply
 

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