Solution For Median Of Two Sorted Arrays
The problem “Median of Two Sorted Arrays” on LeetCode requires finding the median of two sorted arrays of equal or different length.
The median of a set of numbers is the middle number (or the average of the two middle numbers) in a sorted list of those numbers.
Approach:
The problem requires finding the median of two sorted arrays. There are several approaches to solve the problem. In this solution, we will use the binary search algorithm to find the median.
Steps:
Check if the length of the two arrays is equal. If it is not equal, then swap the arrays so that the first array is always the smaller one.
Use binary search to find the partition position of the two arrays such that the sum of the size of the left half of the partitions is equal to the sum of the size of the right half of the partitions.
If the total size of both arrays is even, then the median will be the average of the maximum of the left partition and the minimum of the right partition.
If the total size of both arrays is odd, then the median will be the maximum of the left partition.
Code:
“`
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// Ensuring nums1 is always shorter or equal to nums2
if(nums1.length > nums2.length) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
}
int len1 = nums1.length;
int len2 = nums2.length;
int start = 0;
int end = len1;
while(start <= end) {
int partitionX = (start + end)/2;
int partitionY = (len1 + len2 + 1)/2 - partitionX;
int maxLeftX = partitionX == 0 ? Integer.MIN_VALUE : nums1[partitionX-1];
int minRightX = partitionX == len1 ? Integer.MAX_VALUE : nums1[partitionX];
int maxLeftY = partitionY == 0 ? Integer.MIN_VALUE : nums2[partitionY-1];
int minRightY = partitionY == len2 ? Integer.MAX_VALUE : nums2[partitionY];
if(maxLeftX <= minRightY && maxLeftY <= minRightX) {
if((len1 + len2) % 2 == 0) {
return (double)(Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY))/2;
}
else {
return (double)Math.max(maxLeftX, maxLeftY);
}
}
else if(maxLeftX > minRightY) {
end = partitionX - 1;
}
else {
start = partitionX + 1;
}
}
return -1;
}
“`
Time Complexity: O(log(min(m, n))) where m and n are the lengths of the two arrays.
Step by Step Implementation For Median Of Two Sorted Arrays
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// merge both arrays into a new array
int[] merged = new int[nums1.length + nums2.length];
System.arraycopy(nums1, 0, merged, 0, nums1.length);
System.arraycopy(nums2, 0, merged, nums1.length, nums2.length);
// sort the new array
Arrays.sort(merged);
// get the median
// if the length is odd, it's the middle element
// if the length is even, it's the average of the two middle elements
int length = merged.length;
if (length % 2 == 1) {
return merged[length / 2];
} else {
return (merged[length / 2 - 1] + merged[length / 2]) / 2.0;
}
}
}There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
# merge the two sorted arrays into one sorted array
nums1.extend(nums2)
nums1.sort()
# find the median
length = len(nums1)
if length % 2 == 0:
# even number of elements
median = (nums1[length//2 - 1] + nums1[length//2]) / 2
else:
# odd number of elements
median = nums1[length//2]
return medianThere are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). You may assume nums1 and nums2 cannot be both empty. Example 1: nums1 = [1, 3] nums2 = [2] The median is 2.0 Example 2: nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
class Solution {
public:
double findMedianSortedArrays(vector& nums1, vector& nums2) {
int m = nums1.size();
int n = nums2.size();
if (m > n) {
return findMedianSortedArrays(nums2, nums1);
}
int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
while (iMin <= iMax) {
int i = (iMin + iMax) / 2;
int j = halfLen - i;
if (i < iMax && nums2[j-1] > nums1[i]){
iMin = i + 1;
}
else if (i > iMin && nums1[i-1] > nums2[j]) {
iMax = i - 1;
}
else {
int maxLeft = 0;
if (i == 0) { maxLeft = nums2[j-1]; }
else if (j == 0) { maxLeft = nums1[i-1]; }
else { maxLeft = nums1[i-1] > nums2[j-1] ? nums1[i-1] : nums2[j-1]; }
if ( (m + n) % 2 == 1 ) { return maxLeft; }
int minRight = 0;
if (i == m) { minRight = nums2[j]; }
else if (j == n) { minRight = nums1[i]; }
else { minRight = nums2[j] < nums1[i] ? nums2[j] : nums1[i]; }
return (maxLeft + minRight) / 2.0;
}
}
return 0.0;
}
}; public class Solution {
public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
// TODO: Implement FindMedianSortedArrays function
}
}