Description:
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)).
Examples:
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 in Python:
To find the median of two sorted arrays with a run time complexity of O(log(m+n)), we can use a binary search approach. The key idea is to partition the two arrays in such a way that the elements on the left side of the partition are less than or equal to the elements on the right side of the partition.
Python
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
# Ensure nums1 is the smaller array to make binary search faster
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
low, high = 0, m
while low <= high:
partitionX = (low + high) // 2
partitionY = (m + n + 1) // 2 - partitionX
maxX = float('-inf') if partitionX == 0 else nums1[partitionX - 1]
maxY = float('-inf') if partitionY == 0 else nums2[partitionY - 1]
minX = float('inf') if partitionX == m else nums1[partitionX]
minY = float('inf') if partitionY == n else nums2[partitionY]
# Check if we have partitioned the arrays correctly
if maxX <= minY and maxY <= minX:
# Check if the total number of elements is even or odd
if (m + n) % 2 == 0:
return (max(maxX, maxY) + min(minX, minY)) / 2
else:
return max(maxX, maxY)
elif maxX > minY:
# Move towards left in nums1
high = partitionX - 1
else:
# Move towards right in nums1
low = partitionX + 1
raise ValueError("Input arrays are not sorted")
# Example usage:
sol = Solution()
print(sol.findMedianSortedArrays([1, 3], [2])) # Output: 2.0
print(sol.findMedianSortedArrays([1, 2], [3, 4])) # Output: 2.5Explanation:
- Ensuring nums1 is the smaller array:
- This is done to make sure the binary search is performed on the smaller array for efficiency.
- Binary Search Setup:
- We perform a binary search on the smaller array
nums1withlowstarting at 0 andhighstarting at the length ofnums1.
- We perform a binary search on the smaller array
- Partitions:
partitionXandpartitionYrepresent the positions where the arrays are divided.partitionXis the middle index of the current search range innums1.partitionYis calculated such that the left side of the partition has the same number of elements as the right side (or one more if the total number of elements is odd).
- Max and Min Values:
maxXandmaxYare the maximum elements on the left side of the partitions.minXandminYare the minimum elements on the right side of the partitions.- Edge cases are handled by setting
maxXandmaxYto negative infinity if the partition is at the beginning of an array andminXandminYto positive infinity if the partition is at the end of an array.
- Correct Partition Check:
- If the maximum element on the left side of
nums1is less than or equal to the minimum element on the right side ofnums2and vice versa, the correct partition is found. - If the total number of elements is even, the median is the average of the maximum element on the left side and the minimum element on the right side.
- If the total number of elements is odd, the median is the maximum element on the left side.
- If the maximum element on the left side of
- Adjusting the Search Range:
- If
maxXis greater thanminY, we move the partition innums1to the left. - If
maxYis greater thanminX, we move the partition innums1to the right.
- If
By using this approach, we achieve the desired O(log(m+n)) time complexity.
Solution in Javascript:
JavaScript
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
// Ensure nums1 is the smaller array to make the binary search faster
if (nums1.length > nums2.length) {
[nums1, nums2] = [nums2, nums1];
}
let m = nums1.length;
let n = nums2.length;
let low = 0;
let high = m;
while (low <= high) {
let partitionX = Math.floor((low + high) / 2);
let partitionY = Math.floor((m + n + 1) / 2) - partitionX;
let maxX = (partitionX === 0) ? -Infinity : nums1[partitionX - 1];
let maxY = (partitionY === 0) ? -Infinity : nums2[partitionY - 1];
let minX = (partitionX === m) ? Infinity : nums1[partitionX];
let minY = (partitionY === n) ? Infinity : nums2[partitionY];
// Check if we have partitioned the arrays correctly
if (maxX <= minY && maxY <= minX) {
// Check if the total number of elements is even or odd
if ((m + n) % 2 === 0) {
return (Math.max(maxX, maxY) + Math.min(minX, minY)) / 2;
} else {
return Math.max(maxX, maxY);
}
} else if (maxX > minY) {
// Move towards left in nums1
high = partitionX - 1;
} else {
// Move towards right in nums1
low = partitionX + 1;
}
}
throw new Error("Input arrays are not sorted");
};
// Example usage:
console.log(findMedianSortedArrays([1, 3], [2])); // Output: 2.0
console.log(findMedianSortedArrays([1, 2], [3, 4])); // Output: 2.5Solution in Java:
Java
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// Ensure nums1 is the smaller array to make the binary search faster
if (nums1.length > nums2.length) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
}
int m = nums1.length;
int n = nums2.length;
int low = 0;
int high = m;
while (low <= high) {
int partitionX = (low + high) / 2;
int partitionY = (m + n + 1) / 2 - partitionX;
int maxX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
int maxY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
int minX = (partitionX == m) ? Integer.MAX_VALUE : nums1[partitionX];
int minY = (partitionY == n) ? Integer.MAX_VALUE : nums2[partitionY];
// Check if we have partitioned the arrays correctly
if (maxX <= minY && maxY <= minX) {
// Check if the total number of elements is even or odd
if ((m + n) % 2 == 0) {
return ((double)Math.max(maxX, maxY) + Math.min(minX, minY)) / 2;
} else {
return (double)Math.max(maxX, maxY);
}
} else if (maxX > minY) {
// Move towards left in nums1
high = partitionX - 1;
} else {
// Move towards right in nums1
low = partitionX + 1;
}
}
throw new IllegalArgumentException("Input arrays are not sorted");
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.findMedianSortedArrays(new int[]{1, 3}, new int[]{2})); // Output: 2.0
System.out.println(sol.findMedianSortedArrays(new int[]{1, 2}, new int[]{3, 4})); // Output: 2.5
}
}Solution in C#:
C#
public class Solution {
public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
// Ensure nums1 is the smaller array to make the binary search faster
if (nums1.Length > nums2.Length) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
}
int m = nums1.Length;
int n = nums2.Length;
int low = 0;
int high = m;
while (low <= high) {
int partitionX = (low + high) / 2;
int partitionY = (m + n + 1) / 2 - partitionX;
int maxX = (partitionX == 0) ? int.MinValue : nums1[partitionX - 1];
int maxY = (partitionY == 0) ? int.MinValue : nums2[partitionY - 1];
int minX = (partitionX == m) ? int.MaxValue : nums1[partitionX];
int minY = (partitionY == n) ? int.MaxValue : nums2[partitionY];
// Check if we have partitioned the arrays correctly
if (maxX <= minY && maxY <= minX) {
// Check if the total number of elements is even or odd
if ((m + n) % 2 == 0) {
return ((double)Math.Max(maxX, maxY) + Math.Min(minX, minY)) / 2;
} else {
return (double)Math.Max(maxX, maxY);
}
} else if (maxX > minY) {
// Move towards left in nums1
high = partitionX - 1;
} else {
// Move towards right in nums1
low = partitionX + 1;
}
}
throw new ArgumentException("Input arrays are not sorted");
}
}