Problem
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)).
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.
Constraints:
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106
Solution 1
public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
// find the median merging point
var merged = new List<int>();
merged.AddRange(nums1);
merged.AddRange(nums2);
merged.Sort();
if (merged.Count % 2 == 0) {
var item1 = merged.ElementAt(merged.Count/2);
var item2 = merged.ElementAt(merged.Count/2 - 1);
return ((double)(item1+item2))/2;
} else {
return merged.ElementAt((int)(merged.Count/2));
}
}Solution 2 (Only C# data structure is different)
public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
var mergedArray = nums1.Concat(nums2).ToArray();
Array.Sort(mergedArray);
if (mergedArray.Length % 2 == 0) {
var item1 = mergedArray.ElementAt(mergedArray.Length/2);
var item2 = mergedArray.ElementAt(mergedArray.Length/2 - 1);
return (((double)(item1+item2))/2);
} else {
return mergedArray.ElementAt((int)(mergedArray.Length/2));
}
}Solution 3
public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
// iterate through nums1 and nums2
// get to the mid values in iteration
// and return the median
var medianAt = (nums1.Length + nums2.Length) / 2;
var evenLength = (nums1.Length + nums2.Length) % 2 == 0;
var iteratedOn1 = -1;
var iteratedOn2 = -1;
var medianValues= new int[2];
for (int i = 0; i <= medianAt; i++)
{
if (iteratedOn1 + 1 < nums1.Length || iteratedOn2 + 1 < nums2.Length)
{
if (iteratedOn1 + 1 < nums1.Length && iteratedOn2 + 1 < nums2.Length)
{
if (nums1[iteratedOn1 + 1] <= nums2[iteratedOn2 + 1])
{
iteratedOn1++;
medianValues[0] = medianValues[1];
medianValues[1] = nums1[iteratedOn1];
}
else
{
iteratedOn2++;
medianValues[0] = medianValues[1];
medianValues[1] = nums2[iteratedOn2];
}
} else if (iteratedOn1 + 1 < nums1.Length)
{
iteratedOn1++;
medianValues[0] = medianValues[1];
medianValues[1] = nums1[iteratedOn1];
} else if (iteratedOn2 + 1 < nums2.Length)
{
iteratedOn2++;
medianValues[0] = medianValues[1];
medianValues[1] = nums2[iteratedOn2];
}
}
}
// get the values from iterated1 and iterated2
return evenLength ? ((double)medianValues[0] + medianValues[1]) / 2 : medianValues[1];
}Solution 4 (More optimized version of 3)
public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
// iterate through nums1 and nums2
// get to the mid values in iteration
// and return the median
var medianAt = (nums1.Length + nums2.Length) / 2;
var evenLength = (nums1.Length + nums2.Length) % 2 == 0;
var iteratedOn1 = -1;
var iteratedOn2 = -1;
var medianValues= new int[2];
for (int i = 0; i <= medianAt; i++)
{
if (iteratedOn1 + 1 < nums1.Length || iteratedOn2 + 1 < nums2.Length)
{
if (iteratedOn1 + 1 < nums1.Length && iteratedOn2 + 1 < nums2.Length)
{
if (nums1[iteratedOn1 + 1] <= nums2[iteratedOn2 + 1])
{
iteratedOn1++;
medianValues[0] = medianValues[1];
medianValues[1] = nums1[iteratedOn1];
}
else
{
iteratedOn2++;
medianValues[0] = medianValues[1];
medianValues[1] = nums2[iteratedOn2];
}
} else if (iteratedOn1 + 1 < nums1.Length)
{
iteratedOn1++;
medianValues[0] = medianValues[1];
medianValues[1] = nums1[iteratedOn1];
// We may skip further iterations.
// because further iterations will only run this block
var iterationsRemaining = medianAt - i;
// Find the next value
if (iteratedOn1 != iteratedOn1 + iterationsRemaining)
{
iteratedOn1 += iterationsRemaining;
medianValues[0] = medianValues[1];
medianValues[1] = nums1[iteratedOn1];
if (iterationsRemaining > 1)
{
medianValues[0] = nums1[iteratedOn1-1];
}
}
break;
}
else if (iteratedOn2 + 1 < nums2.Length)
{
iteratedOn2++;
medianValues[0] = medianValues[1];
medianValues[1] = nums2[iteratedOn2];
// We may skip further iterations.
// because further iterations will only run this block
var iterationsRemaining = medianAt - i;
if (iteratedOn2 != iteratedOn2 + iterationsRemaining)
{
iteratedOn2 += iterationsRemaining;
medianValues[0] = medianValues[1];
medianValues[1] = nums2[iteratedOn2];
if (iterationsRemaining > 1)
{
medianValues[0] = nums2[iteratedOn2-1];
}
}
break;
}
}
}
// get the values from iterated1 and iterated2
return evenLength ? ((double)medianValues[0] + medianValues[1]) / 2 : medianValues[1];
}