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
}
}
}
An intriguing discussion is definitely worth comment. I think that you should publish more about this topic, it might not be a taboo subject but generally people do not speak about these subjects. To the next! All the best!!
Right here is the perfect webpage for anybody who wishes to understand this topic. You know so much its almost hard to argue with you (not that I really will need toÖHaHa). You definitely put a fresh spin on a subject which has been written about for decades. Wonderful stuff, just excellent!
You ought to take part in a contest for one of the greatest blogs on the web. Im going to highly recommend this site!
Im more than happy to find this page. I want to to thank you for ones time for this fantastic read!! I definitely appreciated every bit of it and i also have you saved to fav to look at new things in your web site.