Difficulty – Hard
Median of Two Sorted Arrays: 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.
Table of Contents
Median of Two Sorted Arrays Problem Solution
Problem Solution In Python
class Solution:
# @return a float
def findMedianSortedArrays(self, A, B):
med1 = med2 = i = j = 0
n = len(A) + len(B)
while (i + j) <= n / 2:
if i < len(A) and j < len(B):
med2 = med1
if A[i] < B[j]:
med1 = A[i]
i += 1
else:
med1 = B[j]
j += 1
elif i < len(A):
med2 = med1
med1 = A[i]
i += 1
elif j < len(B):
med2 = med1
med1 = B[j]
j += 1
if n % 2 == 0:
return (med1 + med2) / 2.0
else:
return med1
Problem Solution In Java
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i=0;i<nums1.length;i++)
{
list.add(nums1[i]);
}
for(int i=0;i<nums2.length;i++)
{
list.add(nums2[i]);
}
Collections.sort(list);
int size=list.size();
if (size % 2 == 1) return (double) list.get(size/2);
return (double) (list.get((size/2)-1) + list.get(size/2) )/2;
}
}
Problem Solution In C++
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
nums1.insert(nums1.begin(), nums2.begin(), nums2.end());
sort(nums1.begin(), nums1.end());
int median = nums1.size()/2;
if(nums1.size()%2 == 1)
{
return nums1[median];
}
else
{
return (double)(nums1[median]+nums1[median-1])/2;
}
}
Problem Solution In C
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
int len = nums1Size + nums2Size;
int merged[len];
int i = 0, j = 0, idx = 0;
while (i < nums1Size || j < nums2Size) {
if (i < nums1Size && j < nums2Size) {
if (nums1[i] < nums2[j]) {
merged[idx++] = nums1[i++];
} else {
merged[idx++] = nums2[j++];
}
} else if (i < nums1Size) {
merged[idx++] = nums1[i++];
} else {
merged[idx++] = nums2[j++];
}
}
if (len % 2 == 0) {
return ((merged[len/2 - 1] + merged[len/2]) / 2.0);
} else {
return merged[len/2];
}
}