Table of contents
Although it's a leetcode hard question, if you have learned the basic pseudocode of MergeSort, then it is very easy for you.
Problem Statement: Given two sorted arrays
nums1andnums2of sizemandnrespectively, 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.
Approach:
merge both the sorted arrays and make sure the merged array is also sorted(easily done by merge sort code)
if the length of the merged array is odd -> median = (merged[len / 2] + merged[len / 2 + 1]) / 2;
if the length of the merged array is even -> simply return the middle element. median = merged[len / 2];
Code:
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int mix[] = merge(nums1, nums2);
int len = mix.length;
double median = 0.0;
if(len % 2 == 0){ //even
median = (double)(mix[(len - 1) / 2] + mix[((len - 1) / 2) + 1]) / 2;
}
else{
median = mix[(len- 1) / 2];
}
return median;
}
int[] merge(int[] one, int[] two){
int[] mix = new int[one.length + two.length];
int i = 0; int j = 0;
int k = 0;
while(i < one.length && j < two.length){
if(one[i] < two[j]){
mix[k] = one[i];
i++;
// k++;
}
else{
mix[k] = two[j];
j++;
}
k++;
}
while(i < one.length){
mix[k] = one[i];
i++;
k++;
}
while(j < two.length){
mix[k] = two[j];
j++;
k++;
}
return mix;
}
}