[理工] [資結]-94交大資工

[NOtWorThy (分子小於64)]

如題  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
推 psalms945:我也覺得答案有錯應該一個>一個<
推 smalling:> < 對