论坛 › C/C++ › 寻找中间数的算法

galaxywar 发表于 2008-02-02 06:03

一样长的话, 找第一行的中间数就行了;
如果第一行个数为偶数, 那这行中间数有两个, 取他们俩之间那个, 也就是第二行的位于第一个以下的那个.

zgongjin 发表于 2008-02-07 21:13

收下了

tcs_chen 发表于 2008-02-11 03:31

原帖由 emacsnw 于 2008-2-1 17:45 发表 http://bbs.chinaunix.net/images/common/back.gif


类似二分法，假设A和B一样长，因为A，B已经有序，直接找到x = median(A)和y = median(B)，若 x == y，返回 x。不然假设 x < y，则只留下A的后半段和B的前半段，递归，问题规模减半。 T = O(1) + T， ...

正解
可以结贴了 ：）

jigloo 发表于 2008-02-11 19:58

这类火星问题建议先搜索一下csdn

cjaizss 发表于 2008-02-11 20:27

原帖由 jigloo 于 2008-2-11 19:58 发表 http://bbs.chinaunix.net/images/common/back.gif
这类火星问题建议先搜索一下csdn
这是算法级的讨论，不关csdn啥事

jigloo 发表于 2008-02-11 20:33

呃？我隐约感到犯了忌讳。

BenBear 发表于 2008-03-10 11:13

std::nth_element() 挺好的……

sunnyfun 发表于 2008-03-10 15:19

北京大学2006年计算机软件基础考研试题
主要思想确实是折半查找，比较两个数列的中位数，比较大小，而后，据此截出两个数组的各一半，再进行递归。
网上搜到的，呵呵。

tyc611 发表于 2008-03-10 18:50

算法导论第二版，习题9.3-8

tyz 发表于 2008-05-31 23:40

怎么感觉和大学学算法时候第一个实验一样呢

查看完整版本: 寻找中间数的算法