Sponsored
Sponsored
This approach leverages binary search to reduce the problem to a smaller size, achieving the desired O(log(m + n)) complexity. The strategy involves performing binary search on the smaller array to find the perfect partition point.
Time complexity: O(log(min(m,n))). Space complexity: O(1).
1public class Solution {
2 public double findMedianSortedArrays(int[] nums1, int[] nums2) {
3 if (nums1.length > nums2.length) {
4 return findMedianSortedArrays(nums2, nums1);
5 }
6 int x = nums1.length;
7 int y = nums2.length;
8 int low = 0, high = x;
9 while (low <= high) {
10 int partitionX = (low + high) / 2;
11 int partitionY = (x + y + 1) / 2 - partitionX;
12 int maxX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
13 int minX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];
14 int maxY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
15 int minY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];
16 if (maxX <= minY && maxY <= minX) {
17 if ((x + y) % 2 == 0) {
18 return ((double)Math.max(maxX, maxY) + Math.min(minX, minY)) / 2;
19 } else {
20 return (double)Math.max(maxX, maxY);
21 }
22 } else if (maxX > minY) {
23 high = partitionX - 1;
24 } else {
25 low = partitionX + 1;
26 }
27 }
28 throw new IllegalArgumentException("Input arrays are not sorted.");
29 }
30}Similar to C++, the Java implementation handles partitioning by binary search over the smaller array, iteratively refining where elements split across the two sorted arrays to compute the median.
This approach focuses on merging the two sorted arrays as naturally done in merge sort, and then finding the median directly from the merged result. Though this solution has a higher time complexity, it's easier to implement and understand.
Time complexity: O(m + n). Space complexity: O(m + n).
1#
The C implementation uses an auxiliary array to merge the two sorted arrays into one. After merging, we calculate the median of the merged array based on its even or odd length. Memory allocation and deallocation are crucial to manage space efficiently.