• 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

if (nums1.size() % 2 == 1) {
nums1.insert(nums1.begin() + nums1.size()/2, nums1[nums1.size()/2]);
}

if (nums2.size() % 2 == 1) {
nums2.insert(nums2.begin() + nums2.size()/2, 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