快速求两有序数组合并后的中位数

gxqcn

先解释一下“中位数”的概念： 　　把n个数据按大小顺序排列，处于最中间位置的一个数据（或）叫做这组数据的中位数（median）。 中位数仅与数据排列位置有关，当一组数据从小到大排列后，最中间的数据为中位数（偶数个数据取最中间两个的平均数)。 现在的问题是：给出两个已排序的数组A和B，要求快速得到它们合并后的中位数？ （更一般的，如何快速得到两有序数组合并排序后的任意某个位置上的数据？） 大家有空时讨论讨论。 这是我自编的，也许在某个时候某个领域会有用。

无心人

好像很简单的样子

mathe

csdn里面好像讨论过的

g99

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 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)

无心人

归并排序就是这个问题的变形吧

kon3155

csdn有个差不多的 http://topic.csdn.net/u/20090220 ... a-8f9fcfec7a2b.html

litaoye

以前用2分写过1个 http://topic.csdn.net/u/20090117 ... 8-359d3927c145.html