两个有序数组中找第n个数（其中n小于任何一个数组的长度）
有数组A和B，都是按从小到大的排序。现在需要从这两个数组中找到第n大的数。最简单的做法：
逐次比较A和B两个数组，并移动比较指针，直到能找到第n个数。这样的算法复杂度为O(n)
更有效的方法在二楼说（如果能占上的话）
O(lgn)的算法
1. 在A、B中分别取长度为n/2的部分，比较A和B，如相等，则A或B为所求。2. 不失一般性，假设A<B，在A之后取多n/4个数，而B则取前n/4个数，比较A[(3n)/4]和B的值，如果相等，则找到所求，否则转3
3. 假设这时B < A[(3n)/4]，则在B之取多B个数，而A后取多A个数，比较之。。。。
最多经过lg(n)次的比较后，我们可以得到排第n位的那个数了。算法描述：
假设第k次比较时，A数组取的位置为x，而B数组取的位置为y，不失一般性，假设A < B，则下次比较的位置为：
A
B，注意，这里需要使 x + n/(2^k) + y - n/(2^k) == n，而因为整除问题，需要做一定的调节。
直到 n/2^k==0
而k=1时, x = n/2, y = n/2
显然，这样的算法时间复杂度为 O(lg(n)) 对于3个数组，则每次递增或递减的pace可以设为n/3^k，对于s个数组，可以设定为n/s^k。。。。这个没有验算过。 同样找第k大的数，要是只有一个数组，但数组是无序的呢？ 原帖由 klux 于 20-5-2009 20:29 发表 http://www.freeoz.org/forum/images/common/back.gif
同样找第k大的数，要是只有一个数组，但数组是无序的呢？ 先排序:lol 原帖由 klux 于 20-5-2009 20:29 发表 http://www.freeoz.org/forum/images/common/back.gif
同样找第k大的数，要是只有一个数组，但数组是无序的呢？
这样的题目如果不是要考你的应变能力，就是考你的记忆力了。hoho~
首先，最简单、最容易想到的算法就是先排序，然后再给出目标元素。
随便找一种O(nlogn)的排队算法，比如插入排队，于是我们可以得到一个
时间复杂性为O(nlogn)的算法
然后，我们可以通过学习/记忆，知道有一种随机选取算法。在队列中随便找
一个数，如x，用x来分割队列成两部分，比x小的放在左，比x大的放在右，
如果最后发现x所在的位置就是我们需要的位置，那么就得到了我们所要的。
否则，如果x比我们想要的r值小，则在右边再选一个x值进行同样的分割，
否则，在x的左边进行相同的操作。
这种方法的worst-case为O(n^2)，但由于我们通过随机选择，所以，可以用
均值/期望值来作为算法的复杂度，可以证明是O(n)。有人要求证明吗？如果我
还没有疯掉，我可能在下一楼给出证明。
如果考官还不满意这个“期望值”为O(n)的算法，要求你给出一个worst-case
的算法，而你又没有记得的话，我建议你回家先吧。因为worst-case为O(n)
的算法是计算机算法的一个突破，在1973年由5个变态搞出来，其中两个是
Standford教授，一个是普林斯顿，一个是MIT的，还有一个是CMU的。
这个算法的大致做法是把所有n个元素分成5组，并行列出：
o o o o o o o o o o o o o
o o o o o o o o o o o o o
o o o o o o o o o o o o o
o o o o o o o o o o o o
o o o o o o o o o o o o
对每一列的元素进行中间元素的查找，把找到的中间元素放在中间。
然后对中间一行的中间元素进行中值查找（即在n/5个元素中做中值查找），
把找到的中值置中（连同其对应的列）。于是可以得到左上角的 3 * n / 10个元素
小于中值，而右下角的 3 * n / 10 个元素大于中值。如果你要找的元素在1 ~ 7n/10
之间，就不要在右下角找，如果你要找的元素在 3n/10 ~ n 之间，就不要在左上角找。
由这样的方法，递归得到你要的第r个元素。
可证明，这样的操作能在线性时间内获得第 r 个元素。希望我没有表述错误。
[ 本帖最后由 key 于 20-5-2009 23:04 编辑 ] 赞，都讲到了 原帖由 klux 于 20-5-2009 23:10 发表 http://www.freeoz.org/forum/images/common/back.gif
赞，都讲到了
谢谢你提了这个问题，我刚才翻书去了:L :L :D ;P 原帖由 key 于 20-5-2009 23:12 发表 http://www.freeoz.org/forum/images/common/back.gif
谢谢你提了这个问题，我刚才翻书去了:L :L :D ;P
:zan
你就是我们的key啊:good
key兄现在研究什么领域呢？你功底真扎实啊！ 然后，我们可以通过学习/记忆，知道有一种随机选取算法。在队列中随便找
一个数，如x，用x来分割队列成两部分，比x小的放在左，比x大的放在右，
如果最后发现x所在的位置就是我们需要的位置，那么就得到了我们所要的。
否则，如果x比我们想要的r值小，则在右边再选一个x值进行同样的分割，
否则，在x的左边进行相同的操作。
这种方法的worst-case为O(n^2)，但由于我们通过随机选择，所以，可以用
均值/期望值来作为算法的复杂度，可以证明是O(n)。有人要求证明吗？如果我
还没有疯掉，我可能在下一楼给出证明。
我尝试证明一下这个东西。很容易证明，随机取得的x可以把队列分割后，前半部分刚好有k个元素的概率为
E = 1/n，这里 Xk表示为随机取得的x可以把队列分割成前半部分恰好有k个元素的随机变量。
一次操作，可能得到的分割情况有：(0, n-1), (1, n-2), ..., (k-1, n-k), ..., (n-1, 0)，共n中情况，
分割后，最坏的情况是要找到的r在大的那边，这样下一次分割的 n 值就为 max(k-1, n-k)。
一次分割操作所需的时间复杂度为 O(n)，所以整个查找时间T(n)为
T(n) <= sum(Xk * T(max(k-1, n-k)) + O(n)(1)
这里sum是从k=1 to n的。
对(1)式求期望值，得到
E <= E + O(n) (2)
= E * sum(E) + O(n) (3)
= (1/n) * sum(E) + O(n)(4)
= (2/n) * sum(E) + O(n) (5)这里的sum表示的是k = n/2 to n这部分的值
这个证明的目标是E = O(n)，那这里我们就设定T(k) = ck，如果(5)代入后成立，则证明成功
代入后得到：
E <= (2/n) * sum(E) + O(n) = (2/n) * c * sum(k) + 0(n) (6)
显然有sum(k) == (3/8)n^2（等差数列求和）
E <= (2/n) * c * (3/8) n + O(n) = (3/4) * c * n + O(n) = c * n - ((1/4)*c*n - O(n)) (7)
由7式可知，当c为足够大的数时，不等式成立，由此可证明 E = O(n) 原帖由 coredump 于 20-5-2009 23:52 发表 http://www.freeoz.org/forum/images/common/back.gif
:zan
你就是我们的key啊:good
key兄现在研究什么领域呢？你功底真扎实啊！
过奖了，都是google + 一大堆书的结果。哪可能记得这么多东西呢。
最近闲置在家，以看书为乐。市场不好，加之自己不太了解市场，只能先闲置一段时间了。 找到资料都能理解的话，也是牛人了。 原帖由 key 于 20-5-2009 20:25 发表 http://www.freeoz.org/forum/images/common/back.gif
对于3个数组，则每次递增或递减的pace可以设为n/3^k，对于s个数组，可以设定为n/s^k。。。。这个没有验算过。
我觉得这个方法不错，但对多个数组的比较会有困难。如三个数组的n/3 position的比较结果不是ＢＩＮＡＲＹ的值。那如何决定后续指针的移动方向。 原帖由 key 于 20-5-2009 23:00 发表 http://www.freeoz.org/forum/images/common/back.gif
这个算法的大致做法是把所有n个元素分成5组，并行列出：
o o o o o o o o o o o o o
o o o o o o o o o o o o o
o o o o o o o o o o o o o
o o o o o o o o o o o o
o o o o o o o o o o o o
对每一列的元素进行中间元素的查找，把找到的中间元素放在中间。
然后对中间一行的中间元素进行中值查找（即在n/5个元素中做中值查找），
把找到的中值置中（连同其对应的列）。。。
》》》
我对每列（n/5个元素）中间元素的找法有怀疑。如何保证在线性时间找到非排序的列的中间元素，即在n/5个元素中找第n/10个元素。 找个O(N)排序算法不是很好吗 原帖由 decisiontree 于 21-5-2009 13:44 发表 http://www.freeoz.org/forum/images/common/back.gif
我觉得这个方法不错，但对多个数组的比较会有困难。如三个数组的n/3 position的比较结果不是ＢＩＮＡＲＹ的值。那如何决定后续指针的移动方向。
这个问题不难解决，如果是两个数组，那可以一个天一个地（即ceiling/floor）即可，如果是三个数字，那就可以按顺序0,1,2这样来排余数。
总之，想办法让总长度为n即可。显然，要做到这一点并不难，只是做个决定怎样摆就行了。 我对每列（n/5个元素）中间元素的找法有怀疑。如何保证在线性时间找到非排序的列的中间元素，即在n/5个元素中找第n/10个元素。
这个问题是一个递归问题。先假设T(n)为线性，那当然我们可以用线性的时间处理T(n/5)了。 原帖由 lavahx 于 21-5-2009 14:21 发表 http://www.freeoz.org/forum/images/common/back.gif
找个O(N)排序算法不是很好吗
你说得很对。O(n)排序真的很神奇，不过三种典型的O(n)排序，包括计数排序、Radix排序和Bucket排序都有一定的条件制约。
比如Radix排序，我需要找一个合适的radix来排。从某种意义上，通用性受制约。
当然，这应该是一种选择。 原帖由 key 于 21-5-2009 17:03 发表 http://www.freeoz.org/forum/images/common/back.gif
这个问题不难解决，如果是两个数组，那可以一个天一个地（即ceiling/floor）即可，如果是三个数字，那就可以按顺序0,1,2这样来排余数。
总之，想办法让总长度为n即可。显然，要做到这一点并不难，只是做个决定怎 ...
呵呵，恕我愚笨。我知道总长度为n。请明确解释下三个数组的问题。特别是排在中间那个数组的指针走向，向左走还是向右走。然后看看这个办法能不能用到一百一千个数组里。 原帖由 decisiontree 于 21-5-2009 18:17 发表 http://www.freeoz.org/forum/images/common/back.gif
呵呵，恕我愚笨。我知道总长度为n。请明确解释下三个数组的问题。特别是排在中间那个数组的指针走向，向左走还是向右走。然后看看这个办法能不能用到一百一千个数组里。
相信没有什么东西比一段代码更有说服力了。我用C语言实现了上面说的那个算法。1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <unistd.h>
4 #include <sys/types.h>
5 #include <time.h>
6 #include <values.h>
7 #include <string.h>
8
9
10 /*
11* randomly choose the len of array A , Band C from 1024 to 2048
12* and randomly choose the value of <i>th from 100 to 500
13*
14* note that the start index of C array is 0 and the start number of ith is 1
15*
16*/
17
18 void generate(int x[], size_t len)
19 {
20 int k;
21
22 for(k=0; k<len; k++)
23 {
24 x = rand() % 9999;
25 }
26 }
27
28 int value_compare(const void * v1, const void * v2)
29 {
30 const int * vv1 = (const int *)v1;
31 const int * vv2 = (const int *)v2;
32
33 return (* vv1) - (* vv2);
34 }
35
36 int main(int argc, char ** argv)
37 {
38 int len, tlen;
39 int * seq;
40 int base;
41 int ith;
42 int count, lowest_pace;
43 int k;
44 int curpace, diff;
45
46 srand(time(NULL));
47
48 tlen = 0;
49 for(k=0; k<3; k++)
50 {
51 len = rand() % 1024 + 1024;
52 seq = (int *)malloc(len * sizeof(int));
53 generate(seq, len);
54 qsort(seq, len, sizeof(int), value_compare);
55 tlen += len;
56 }
57
58 ith = rand() % 400 + 100;
59
60 //debug
61 printf("N = %d, A = %d, B = %d, C = %d, ith = %d\n", tlen, len, len, len, ith);
62
63 count = 0;
64 lowest_pace = ith / 3;
65 base = base = base = 0;
66
67 int min, minSeq;
68
69 while(lowest_pace > 1)
70 {
71 printf("DEBUG lowest_pace = %d, A_base = %d, B_base = %d, C_base = %d\n",
72 lowest_pace, base, base, base);
73
74 diff = ith - (base + base + base + 3 * lowest_pace);
75 int pace;
76 int k;
77
78 minSeq = -1;
79
80 pace = pace = pace = lowest_pace;
81
82 for(k=0;diff>0; --diff, k++)
83 {
84 pace++;
85 }
86
87 int total_pace;
88
89 for(k=0; k<3; k++)
90 {
91 total_pace = base + pace;
92 }
93
94
95 min = MAXINT;
96
97 for(k=0; k<3; k++)
98 {
99 if(seq] < min)
100 {
101 min = seq];
102 minSeq = k;
103 }
104 }
105
106 base += pace;
107
108 curpace = 0;
109 for(k=0; k<3; k++)
110 {
111 curpace += base;
112 }
113
114 lowest_pace = (ith - curpace) / 3;
115 }
116
117 curpace = base + base + base;
118 diff = ith - curpace;
119
120
121 k = 0;
122
123 while(diff > 0)
124 {
125 min = MAXINT;
126 minSeq = -1;
127
128 for(k=0; k<3; k++)
129 {
130 if(min > seq])
131 {
132 min = seq];
133 //base ++;
134 minSeq = k;
135 }
136 }
137
138 base ++;
139 diff --;
140
141 }
142
143 printf("\n");
144 printf("<%d>th number is %d, seq is %d, base = %d, base = %d, base = %d\n",
145 ith, seq-1], minSeq,base, base, base);
146
147 int * nseq = (int *)malloc(sizeof(int) * tlen);
148 memcpy(nseq, seq, sizeof(int) * len);
149 memcpy((char *)nseq + len * sizeof(int), seq, sizeof(int) * len);
150 memcpy((char *)nseq + len * sizeof(int) + len * sizeof(int), seq, sizeof(int) * len);
151
152 qsort(nseq, tlen, sizeof(int), value_compare);
153
154 printf("<%d>th should be %d\n", ith, nseq);
155
156 return 0;
157 }测试结果一N = 4242, A = 1102, B = 1892, C = 1248, ith = 144
DEBUG lowest_pace = 48, A_base = 0, B_base = 0, C_base = 0
DEBUG lowest_pace = 32, A_base = 0, B_base = 48, C_base = 0
DEBUG lowest_pace = 21, A_base = 0, B_base = 48, C_base = 32
DEBUG lowest_pace = 14, A_base = 22, B_base = 48, C_base = 32
DEBUG lowest_pace = 9, A_base = 22, B_base = 62, C_base = 32
DEBUG lowest_pace = 6, A_base = 22, B_base = 62, C_base = 41
DEBUG lowest_pace = 4, A_base = 22, B_base = 62, C_base = 47
DEBUG lowest_pace = 2, A_base = 27, B_base = 62, C_base = 47
<144>th number is 323, seq is 1, base = 29, base = 68, base = 47
<144>th should be 323测试结果二N = 5364, A = 1788, B = 2025, C = 1551, ith = 220
DEBUG lowest_pace = 73, A_base = 0, B_base = 0, C_base = 0
DEBUG lowest_pace = 49, A_base = 0, B_base = 73, C_base = 0
DEBUG lowest_pace = 32, A_base = 49, B_base = 73, C_base = 0
DEBUG lowest_pace = 22, A_base = 49, B_base = 73, C_base = 32
DEBUG lowest_pace = 14, A_base = 71, B_base = 73, C_base = 32
DEBUG lowest_pace = 9, A_base = 71, B_base = 88, C_base = 32
DEBUG lowest_pace = 6, A_base = 71, B_base = 88, C_base = 41
DEBUG lowest_pace = 4, A_base = 71, B_base = 88, C_base = 47
DEBUG lowest_pace = 3, A_base = 76, B_base = 88, C_base = 47
DEBUG lowest_pace = 2, A_base = 76, B_base = 91, C_base = 47
<220>th number is 418, seq is 2, base = 77, base = 94, base = 49
<220>th should be 418测试结果三：N = 4915, A = 2045, B = 1040, C = 1830, ith = 345
DEBUG lowest_pace = 115, A_base = 0, B_base = 0, C_base = 0
DEBUG lowest_pace = 76, A_base = 115, B_base = 0, C_base = 0
DEBUG lowest_pace = 51, A_base = 115, B_base = 0, C_base = 76
DEBUG lowest_pace = 34, A_base = 115, B_base = 51, C_base = 76
DEBUG lowest_pace = 22, A_base = 150, B_base = 51, C_base = 76
DEBUG lowest_pace = 15, A_base = 150, B_base = 51, C_base = 98
DEBUG lowest_pace = 10, A_base = 150, B_base = 66, C_base = 98
DEBUG lowest_pace = 7, A_base = 150, B_base = 66, C_base = 108
DEBUG lowest_pace = 4, A_base = 157, B_base = 66, C_base = 108
DEBUG lowest_pace = 3, A_base = 157, B_base = 66, C_base = 112
DEBUG lowest_pace = 2, A_base = 161, B_base = 66, C_base = 112
<345>th number is 655, seq is 2, base = 164, base = 67, base = 114
<345>th should be 655 原来的算法说可增可减，事实上是不应该减的，而是每次都从各自的base那里开始增一定量。
获取pace的方法也不是通过n/b^k这样的方式，而是通过剩余长度/b的方法
最后就是每次比较后，只有最小的那个队列的base增大，否则某个队列的增长就有可能过快，
导致结果错误（这个证明谁来做一下？）
基于第三点，如果有成百上千个队列，采用这样的方式来查找，可能效率不是太高，
也就是base case的值需要很大，lg(n)的效率才显示出来
相信没有什么东西比一段代码更有说服力了
这个不能认同。数学证明才有说服力。代码受到程序语言与运行环境的约束并不总是准确 原帖由 klux 于 21-5-2009 22:25 发表 http://www.freeoz.org/forum/images/common/back.gif
这个不能认同。数学证明才有说服力。代码受到程序语言与运行环境的约束并不总是准确
哈哈。。。扛王 原帖由 key 于 21-5-2009 21:51 发表 http://www.freeoz.org/forum/images/common/back.gif
原来的算法说可增可减，事实上是不应该减的，而是每次都从各自的base那里开始增一定量。
获取pace的方法也不是通过n/b^k这样的方式，而是通过剩余长度/b的方法
最后就是每次比较后，只有最小的那个队列的base增大， ...
兄弟写代码辛苦了:good 。我看了一百二十多行，被看晕了。:L 汗自己（有COMMNENTS可能会好点）。大概知道你的意思了。但我还没法证明它是线性复杂度。 原帖由 decisiontree 于 22-5-2009 01:57 发表 http://www.freeoz.org/forum/images/common/back.gif
兄弟写代码辛苦了:good 。我看了一百二十多行，被看晕了。:L 汗自己（有COMMNENTS可能会好点）。大概知道你的意思了。但我还没法证明它是线性复杂度。
写代码是最容易的阶段了，hoho~
其实上面说到的有两个不同的问题，这个算法是O(lgn)的复杂度，算法的核心是69行开始至115行的一个while循环，步进的处理在96至114，重点是两点：
1. 找到最小的行
2. 让最小的行的base步进
3. 设置下一次的最短步进距离
而82至85行是用来微调各个队列的步进，使之加起来总和为 n 。这个地方我写得不赖。
由上面的1，2点，确保了每次至少步进lowest_pace的距离。而第3点确保了lowest_pace大致上等于lg(ith)， 整个算法的时间复杂度为lg(ith) 原帖由 key 于 22-5-2009 08:42 发表 http://www.freeoz.org/forum/images/common/back.gif
写代码是最容易的阶段了，hoho~
其实上面说到的有两个不同的问题，这个算法是O(lgn)的复杂度，算法的核心是69行开始至115行的一个while循环，步进的处理在96至114，重点是两点：
1. 找到最小的行
2. 让最小的 ...
不是说两点吗？写出来是三点，哈哈。。。。真是:L :D 原帖由 key 于 21-5-2009 21:51 发表 http://www.freeoz.org/forum/images/common/back.gif
原来的算法说可增可减，事实上是不应该减的，而是每次都从各自的base那里开始增一定量。
获取pace的方法也不是通过n/b^k这样的方式，而是通过剩余长度/b的方法
最后就是每次比较后，只有最小的那个队列的base增大， ...
我觉得减是需要的，最小队列成功步进后，最大队列因该相应步退（如果没有退成比当前最小队列还小的值），才能保证总值n不变。
这么多高人啊，简直要崇拜了。。。
算法复杂度是我的软肋了，一听就头大，都怪数据结构老师长得抱歉、教得也太抱歉了:P 。可是偏偏去年碰到几个面试/笔试就有，有什么比较容易的办法不？大家帮忙给个意见？回复 #28 绿衣 的帖子
学算法得沉得下心，耐着性子，慢慢培养兴趣，还得亲自动手，多写点C代码，这方面我也很差:L同意啊，算法需要多练多看。还是想知道对O( x )括号里那个怎么确定有方法/技巧吗？
如果说对O(n)还有感觉的话，可是n^2、 lgN和更复杂的..具体是怎么算出来的有比较容易掌握的方法吗？很多书和资料只给出个复杂度是多少，实在让我为难啊:L
页:
[1]
2