作者NOtWorThy (分子小於64)
看板Grad-ProbAsk
标题[理工] [资结]-94交大资工
时间Sat Feb 13 19:40:17 2010
如题 94交大资工资结演算法
There are two collections A = {a1, a2, ..., ak} B = {b1, b2, ...., bn}of
k <= n distinct integers selected from {1,2,...,n} Design an O(klogk) algo
to find all the numbers that occur in both A and B.
解答如下
// A' <- sort A
// B' <- sort B
i, j <
C <- null
while(i<=k or j<=k){
if(A'[i]==B'[j])
do add C[i] into C
i++
j++
else if A'[i] > B'[j]
do while(A'[i] <= B'[j]) /* 这边是不是有问题阿?! 我觉得是 ">" */
j++
else
while(A'[i]>=B'[j]) /* 这边也是 */
i++
}
不知道我理解有误还是答案有错
烦请高手帮忙
感激不尽
新年快乐~
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 219.70.230.226
1F：推 psalms945:我也觉得答案有错应该一个>一个< 02/21 12:10
2F：推 smalling:> < 对 02/25 01:18