Example: Input : ar1[] = {-5, 3, 6, 12, 15}
ar2[] = {-12, -10, -6, -3, 4, 10}
The merged array is :
ar3[] = {-12, -10, -6, -5 , -3,
3, 4, 6, 10, 12, 15}
Output : The median is 3.
Solution: Start partitioning the two arrays into two groups of halves. The first half contains some first elements from the first and the second arrays, and the second half contains the rest elements form both arrays. Reach a condition such that, every element in the first half is less than or equal to every element in the second half.
public double FindMedianSortedArrays(int[] nums1, int[] nums2)
{
if (nums1 == null && nums2 == null)
{
return -1;
}
if (nums1.Length == 0 && nums2.Length == 0)
{
return -1;
}
if (nums1.Length <= nums2.Length)
{
return this.FindMedianSortedArraysInternal(nums1, nums2);
}
else
{
return this.FindMedianSortedArraysInternal(nums2, nums1);
}
}
private double FindMedianSortedArraysInternal(int[] nums1, int[] nums2)
{
int minIndex = 0, maxIndex = nums1.Length, nums1Index = 0, nums2Index = 0;
double median = 0;
while (minIndex <= maxIndex)
{
nums1Index = (minIndex + maxIndex) / 2;
nums2Index = ((nums1.Length + nums2.Length + 1) / 2) - nums1Index;
if (nums2Index < 0)
{
maxIndex = nums1Index - 1;
continue;
}
// if num1Index = num1.Length, it means that elements from num1 in the second half is an
// empty set. and if num2Index = 0, it means that elements from num2 in the first half is an
// empty set. so it is necessary to check that, because we compare elements from these two
// groups. Searching on right
if (nums1Index < nums1.Length && nums2Index > 0 && nums2[nums2Index - 1] > nums1[nums1Index])
{
minIndex = nums1Index + 1;
}
// if num1Index = 0, it means that Elements from num1 in the first half is an empty set and if
// num2Index = num2.Length, it means that Elements from num2 in the second half is an
// empty set. so it is necessary to check that, because we compare elements from these two
// groups. searching on left
else if (nums1Index > 0 && nums2Index < nums2.Length && nums2[nums2Index] < nums1[nums1Index - 1])
{
maxIndex = nums1Index - 1;
}
// Found the desired halves
else
{
// this condition happens when we don't have any elements in the first half from num1 so
// we returning the last element in num2 from the first half.
if (nums1Index == 0)
{
median = nums2[nums2Index - 1];
}
// this condition happens when we don't have any elements in the first half from num2 so
// we returning the last element in num1 from the first half.
else if (nums2Index == 0)
{
median = nums1[nums1Index - 1];
}
else
{
median = Math.Max(nums1[nums1Index - 1], nums2[nums2Index - 1]);
}
break;
}
}
// If number of elements is odd there is one middle element.
if ((nums1.Length + nums2.Length) % 2 == 1)
{
return median;
}
// Elements from nums1 in the second half is an empty set.
if (nums1Index == nums1.Length)
{
return (median + nums2[nums2Index]) / 2;
}
// Elements from nums2 in the second half is an empty set.
if (nums2Index == nums2.Length)
{
return (median + nums1[nums1Index]) / 2;
}
return (median + Math.Min(nums1[nums1Index], nums2[nums2Index])) / 2;
}
No comments:
Post a Comment