謝謝你的回答!
不過請問可以指教的詳細一點嗎?因為我還是個學生,懂的不是很全方面,
Space trade-off 是指linked list吧?
那所謂的O(1)和O(N)的差別是什麼??(我是連O(1)都搞不清楚是什麼的人...Orz)
又如何實作呢?
如果可以的話,麻煩再指教一些,謝謝!
一個比較普通的方法, 就是對每個在第二組數列的數, 都去尋找是否有出現在第一組數列中,
而去尋找是否在第一組數列中要找 N 次, 而第二組數列有 N 個數, (註:題目上是用 M 而不是用 N)
所以總共要找 N*N 次, 也就是時間複雜度為 O(N^2) ....
不過因為這兩個數列都是嚴格遞增, 所以你不用找得這麼辛苦,
你可以用兩個變數 i、j 各代表目前找到第一、二組數列的第幾個,
如果第一組數列的第 i 個數 A[i] 比第二組數列的第 j 個數 B[j] 大,
則把 j 加 1 , 再繼續比下去,
而如果 A[i] < B[j] , 則 i 加 1 ,
最後如果 A[i]==B[j] , 則把記錄共同的數有幾個的變數加 1 ,
再把 i、j 同時加 1 , 直到 i 或 j 有一個已經超出數列的範圍為止,
這樣最多就是找 N*2 次, 也就是時間複雜度為 O(N) ,
用這樣的寫法就不會 TLE 了....