Given two sorted arrays nums1
and nums2
of size m
and n
respectively, return the median of the two sorted arrays.
The overall run time complexity should be
O(log (m+n))
.
Example 1:
Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Explanation: merged array = [1,2,3] and median is 2.
Example 2:
Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000 Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Solution:
CPP
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
vector<int>v3;
v3=nums1;
v3.insert(v3.end(), nums2.begin(), nums2.end());
double res;
sort(v3.begin(),v3.end());
int n=v3.size();
if(n%2==0){
int x=n/2;
double a=v3[x-1];
double b=v3[x];
res=(a+b)/2;
return res;
}
else{
return res=v3[n/2];
}
}
};
Java Solution :
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if(nums2.length < nums1.length)
return findMedianSortedArrays(nums2, nums1);
return helper(nums1, 0, nums1.length, nums2);
}
private double helper(int[] nums1, int l, int h, int[] nums2){
while(l <= h){
int m1 = l+(h-l)/2; //# of elements on left in nums1
int m2 = (nums2.length+nums1.length+1)/2-m1; //# of elements on left in nums2
if(m1 > 0 && m2 < nums2.length && nums1[m1-1] > nums2[m2]) //m1 needs to reduced
h = m1-1;
else if(m2 > 0 && m1 < nums1.length && nums2[m2-1] > nums1[m1])
l = m1+1;
else{
int total = nums1.length+nums2.length;
int maxLeft = -Integer.MAX_VALUE;
if(m1 > 0)
maxLeft = Math.max(maxLeft, nums1[m1-1]);
if(m2 > 0)
maxLeft = Math.max(maxLeft, nums2[m2-1]);
if(total % 2 != 0)
return maxLeft;
int minRight = Integer.MAX_VALUE;
if(m1 < nums1.length)
minRight = Math.min(minRight, nums1[m1]);
if(m2 < nums2.length)
minRight = Math.min(minRight, nums2[m2]);
return (maxLeft+minRight)/2.0;
}
}
return 0;
}
java script Solution :
const findMedianSortedArrays = (nums1, nums2) => {
// 1. Find the shorter array of the two lists and make it nums1
// 2. Find a pivot point in nums1 (using binary search)
// 3. pX + pY = (x + y + 1)/2, where x = len(nums1) and y = len(nums2)
if(nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
let [x, y] = [nums1.length, nums2.length];
let [low, high] = [0, x];
while (low <= high) {
let pX = Math.floor((low + high)/2);
let pY = Math.floor((x + y + 1)/2) - pX;
let maxLeftX = (pX === 0)? -Infinity: nums1[pX - 1];
let minRightX = (pX === x)? Infinity: nums1[pX];
let maxLeftY = (pY === 0)? -Infinity: nums2[pY - 1];
let minRightY = (pY === y)? Infinity: nums2[pY];
// Found the required condition
if(maxLeftX <= minRightY && maxLeftY <= minRightX ) {
let maxLeft = Math.max(maxLeftX, maxLeftY);
let minRight = Math.min(minRightX, minRightY);
// for even length
if((x + y) % 2 === 0) {
return (maxLeft + minRight)/2.0;
}
// for odd length
else {
return maxLeft;
}
}
else if(maxLeftX > minRightY) {
high = pX - 1;
}
else {
low = pX + 1
}
}
}