[理工] [資結]-交大94-資工
如題 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
推
02/21 12:10, , 1F
02/21 12:10, 1F
推
02/25 01:18, , 2F
02/25 01:18, 2F