快速求两有序数组合并后的中位数
先解释一下“中位数”的概念：把n个数据按大小顺序排列，处于最中间位置的一个数据（或）叫做这组数据的中位数（median）。
中位数仅与数据排列位置有关，当一组数据从小到大排列后，最中间的数据为中位数（偶数个数据取最中间两个的平均数)。
现在的问题是：给出两个已排序的数组A和B，要求快速得到它们合并后的中位数？
（更一般的，如何快速得到两有序数组合并排序后的任意某个位置上的数据？）
大家有空时讨论讨论。
这是我自编的，也许在某个时候某个领域会有用。 好像很简单的样子 csdn里面好像讨论过的 from CSDN:
Say the two arrays are sorted and increasing, namely A and B.
It is easy to find the median of each array in O(1) time.
Assume the median of array A is m and the median of array B is n.
Then,
1' If m=n, then clearly the median after merging is also m, the algorithm holds.
2' If m <n, then reserve the half of sequence A in which all numbers are greater than
m, also reserve the half of sequence B in which all numbers are smaller than n.
Run the algorithm on the two new arrays.
3' If m>n, then reserve the half of sequence A in which all numbers are smaller than
m, also reserve the half of sequence B in which all numbers are larger than n.
Run the algorithm on the two new arrays.
Time complexity: O(logn) 归并排序就是这个问题的变形吧 csdn有个差不多的
http://topic.csdn.net/u/20090220/13/7f6df674-dbda-4842-b51a-8f9fcfec7a2b.html 以前用2分写过1个
http://topic.csdn.net/u/20090117/10/1562276c-7a1d-4768-9848-359d3927c145.html
页:
[1]