if array length is odd
take element # (length+1)/2
else
take average of element # length/2 and # length/2 - 1
小智 5
中位数:在概率论和统计学中,中位数被描述为将下半部分的样本的较高一半,人口或概率分布分开的数字.
可以通过将所有数字从最低值排列到最高值并选择中间值来找到有限数字列表的中值.为了获得输入数组{12,11,15,10,20}的中值,首先对数组进行排序.排序后我们得到{10,11,12,15,20}.中位数是排序数组的中间元素,即12.
采用具有偶数个元素的数组的中值有不同的约定,一个可以取两个中间值的平均值,或者第一个中间值,或第二个中间值.
让我们看一下不同的方法来获得每个大小为n的两个排序数组的中值.由于我们正在寻找中位数的集合的大小是偶数(2n),我们在所有下面的解决方案中取平均两个中间两个数字.
方法1(合并时简单计数)
使用合并排序的合并过程.在比较两个数组的元素时跟踪计数.如果count变为n(对于2n个元素),我们已达到中位数.获取合并数组中索引n-1和n处元素的平均值.请参阅以下实施.执行:
/* This function returns median of ar1[] and ar2[].
Assumptions in this function:
Both ar1[] and ar2[] are sorted arrays
Both have n elements */
int getMedian(int ar1[], int ar2[], int n)
{
int i = 0; /* Current index of i/p array ar1[] */
int j = 0; /* Current index of i/p array ar2[] */
int count;
int m1 = -1, m2 = -1;
/* Since there are 2n elements, median will be average
of elements at index n-1 and n in the array obtained after
merging ar1 and ar2 */
for(count = 0; count <= n; count++)
{
/*Below is to handle case where all elements of ar1[] are
smaller than smallest(or first) element of ar2[]*/
if(i == n)
{
m1 = m2;
m2 = ar2[0];
break;
}
/*Below is to handle case where all elements of ar2[] are
smaller than smallest(or first) element of ar1[]*/
else if(j == n)
{
m1 = m2;
m2 = ar1[0];
break;
}
if(ar1[i] < ar2[j])
{
m1 = m2; /* Store the prev median */
m2 = ar1[i];
i++;
}
else
{
m1 = m2; /* Store the prev median */
m2 = ar2[j];
j++;
}
}
return (m1 + m2)/2;
}
/* Driver program to test above function */
int main()
{
int ar1[] = {1, 12, 15, 26, 38};
int ar2[] = {2, 13, 17, 30, 45};
printf("%d", getMedian(ar1, ar2, 5)) ;
getchar();
return 0;
}
时间复杂度:O(n)
空间复杂度:O(1)
方法2(通过比较两个数组的中位数)
此方法的工作原理是首先获取两个已排序数组的中位数,然后比较它们.
设ar1和ar2为输入数组.
算法:
1)分别计算输入数组ar1 []和ar2 []的中位数m1和m2.
2)如果m1和m2都相等,那么我们就完成了.返回m1(或m2)
3)如果m1大于m2,则中值存在于以下两个子阵列之一中.
a)从ar1的第一个元素到m1(ar1 [0 ... | n/2 |])
b)从m2到ar2的最后一个元素(ar2 [| n/2 | ... n-1])
4)如果m2大于m1,则中值存在于以下两个子阵列之一中.
a)从m1到ar1的最后一个元素(ar1 [| n/2 | ... n-1])
b)从ar2的第一个元素到m2(ar2 [0 ... | n/2 |])
4)重复上述过程,直到两个子阵列的大小变为2.
5)如果两个数组的大小是2,那么使用下面的公式来得到中位数.
中位数=(max(ar1 [0],ar2 [0])+ min(ar1 1,ar2 1))/ 2
例:
ar1 [] = {1,12,15,26,38}
ar2 [] = {2,13,17,30,45}
对于上述两个阵列,m1 = 15且m2 = 17
对于上面的ar1 []和ar2 [],m1小于m2.因此,中值存在于以下两个子阵列之一中.
[15,26,38]和[2,13,17]
让我们重复上述两个子阵列的过程:
m1 = 26 m2 = 13.
m1大于m2.所以子阵列变成了
[15,26]和[13,17]
现在大小为2,所以中位数=(max(ar1 [0],ar2 [0])+ min(ar1 1,ar2 1))/ 2
=(max(15,13)+ min(26,17))/ 2
=(15 + 17)/ 2
= 16
执行:
int max(int, int); /* to get maximum of two integers */
int min(int, int); /* to get minimum of two integeres */
int median(int [], int); /* to get median of a single array */
/* This function returns median of ar1[] and ar2[].
Assumptions in this function:
Both ar1[] and ar2[] are sorted arrays
Both have n elements */
int getMedian(int ar1[], int ar2[], int n)
{
int m1; /* For median of ar1 */
int m2; /* For median of ar2 */
/* return -1 for invalid input */
if(n <= 0)
return -1;
if(n == 1)
return (ar1[0] + ar2[0])/2;
if (n == 2)
return (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1])) / 2;
m1 = median(ar1, n); /* get the median of the first array */
m2 = median(ar2, n); /* get the median of the second array */
/* If medians are equal then return either m1 or m2 */
if(m1 == m2)
return m1;
/* if m1 < m2 then median must exist in ar1[m1....] and ar2[....m2] */
if (m1 < m2)
return getMedian(ar1 + n/2, ar2, n - n/2);
/* if m1 > m2 then median must exist in ar1[....m1] and ar2[m2...] */
return getMedian(ar2 + n/2, ar1, n – n/2);
}
/* Driver program to test above function */
int main()
{
int ar1[] = {1, 12, 15, 26, 38};
int ar2[] = {2, 13, 17, 30, 45};
printf(“%d”, getMedian(ar1, ar2, 5)) ;
getchar();
return 0;
}
/* Utility functions */
int max(int x, int y)
{
return x > y? x : y;
}
int min(int x, int y)
{
return x > y? y : x;
}
/* Function to get median of a single array */
int median(int arr[], int n)
{
if(n%2 == 0)
return (arr[n/2] + arr[n/2-1])/2;
else
return arr[n/2];
}
时间复杂度:O(logn)
空间复杂度:O(1)
算法范式:分而治之
方法3(通过二进制搜索中位数):
基本思想是,如果给你两个数组ar1 []和ar2 []并知道每个数组的长度,你可以检查一个元素ar1 [i]是否是恒定时间的中位数.假设中位数是ar1 [i].由于数组已排序,因此它大于数组ar1 []中的i-1值.然后,如果它是中位数,它也大于ar2 []中的j = n - i - 1个元素.
它需要不断的时间来检查ar2 [j]
对于两个数组ar1和ar2,首先在ar1 []中进行二进制搜索.如果到达第一个数组的末尾(左侧或右侧)并且没有找到中位数,则在第二个数组ar2 []中开始搜索.
1)使用左右数组索引获取ar1 []的中间元素.
让中间元素的索引为i.
2)计算ar2 []的相应索引j
j = n - i - 1
3)如果ar1 [i]> = ar2 [j]和ar1 [i]
例:
ar1 [] = {1,5,7,10,13}
ar2 [] = {11,15,23,30,45}
ar1 []的中间元素是7.让我们将7与23和30进行比较,因为7小于23和30,在ar1 []中向右移动.在{10,13}进行二进制搜索,这一步将选择10.
现在将10与15和23进行比较.由于10小于15和23,再次向右移动.现在右边只有13个.由于13大于11且小于15,因此在此处终止.我们将中位数设为12(平均值为11和13)实施:
int getMedianRec(int ar1[], int ar2[], int left, int right, int n);
/* This function returns median of ar1[] and ar2[].
Assumptions in this function:
Both ar1[] and ar2[] are sorted arrays
Both have n elements */
int getMedian(int ar1[], int ar2[], int n)
{
return getMedianRec(ar1, ar2, 0, n-1, n);
}
/* A recursive function to get the median of ar1[] and ar2[]
using binary search */
int getMedianRec(int ar1[], int ar2[], int left, int right, int n)
{
int i, j;
/* We have reached at the end (left or right) of ar1[] */
if(left > right)
return getMedianRec(ar2, ar1, 0, n-1, n);
i = (left + right)/2;
j = n – i – 1; /* Index of ar2[] */
/* Recursion terminates here.*/
if(ar1[i] > ar2[j] && (j == n-1 || ar1[i] <= ar2[j+1]))
{
/*ar1[i] is decided as median 2, now select the median 1
(element just before ar1[i] in merged array) to get the
average of both*/
if(ar2[j] > ar1[i-1] || i == 0)
return (ar1[i] + ar2[j])/2;
else
return (ar1[i] + ar1[i-1])/2;
}
/*Search in left half of ar1[]*/
else if (ar1[i] > ar2[j] && j != n-1 && ar1[i] > ar2[j+1])
return getMedianRec(ar1, ar2, left, i-1, n);
/*Search in right half of ar1[]*/
else /* ar1[i] is smaller than both ar2[j] and ar2[j+1]*/
return getMedianRec(ar1, ar2, i+1, right, n);
}
/* Driver program to test above function */
int main()
{
int ar1[] = {1, 12, 15, 26, 38};
int ar2[] = {2, 13, 17, 30, 45};
printf(“%d”, getMedian(ar1, ar2, 5)) ;
getchar();
return 0;
}
时间复杂度:O(logn)
空间复杂度:O(1)
算法范式:分而治之
| 归档时间： |
|
| 查看次数： |
9085 次 |
| 最近记录： |