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).
1#include <stdio.h>
2#include <stdlib.h>
3#include <limits.h>
4
5double findMedianSortedArrays(int* nums1, int m, int* nums2, int n) {
6 if (m > n) {
7 return findMedianSortedArrays(nums2, n, nums1, m);
8 }
9 int imin = 0, imax = m, halfLen = (m + n + 1) / 2;
10 while (imin <= imax) {
11 int i = (imin + imax) / 2;
12 int j = halfLen - i;
13 if (i < m && nums2[j - 1] > nums1[i]) {
14 imin = i + 1;
15 } else if (i > 0 && nums1[i - 1] > nums2[j]) {
16 imax = i - 1;
17 } else {
18 int maxLeft = 0;
19 if (i == 0) { maxLeft = nums2[j - 1]; }
20 else if (j == 0) { maxLeft = nums1[i - 1]; }
21 else { maxLeft = (nums1[i - 1] > nums2[j - 1]) ? nums1[i - 1] : nums2[j - 1]; }
22 if ((m + n) % 2 == 1) {
23 return maxLeft;
24 }
25 int minRight = 0;
26 if (i == m) { minRight = nums2[j]; }
27 else if (j == n) { minRight = nums1[i]; }
28 else { minRight = (nums1[i] < nums2[j]) ? nums1[i] : nums2[j]; }
29 return (maxLeft + minRight) / 2.0;
30 }
31 }
32 return 0.0;
33}In this C solution, we first ensure that we perform the binary search on the smaller of the two arrays to maintain efficiency. We set bounds for `i` and adjust those bounds based on comparisons calculated at each step. The correct partitioning of elements between the two arrays determines 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).
1using System;
2
public class Solution {
public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
int[] mergedArray = new int[nums1.Length + nums2.Length];
int i = 0, j = 0, k = 0;
while (i < nums1.Length && j < nums2.Length) {
if (nums1[i] < nums2[j]) {
mergedArray[k++] = nums1[i++];
} else {
mergedArray[k++] = nums2[j++];
}
}
while (i < nums1.Length) {
mergedArray[k++] = nums1[i++];
}
while (j < nums2.Length) {
mergedArray[k++] = nums2[j++];
}
int totalLength = mergedArray.Length;
if (totalLength % 2 == 0) {
return (mergedArray[totalLength / 2 - 1] + mergedArray[totalLength / 2]) / 2.0;
} else {
return mergedArray[totalLength / 2];
}
}
}The C# solution ensures both arrays are merged into a single sorted array, betting on simple logic rather than clever computation. The process easily lets us check the middle element or average them for the median.