[理工] [algo/演算法] 兩個已排序的陣列找中間值

看板Grad-ProbAsk作者mozzan (mozzan)時間14年前 (2012/01/21 10:55)推噓4(4推 0噓 5→)

留言9則, 5人參與討論串1/1

這是去年公費留學演算法考題 Let A[1..n] and B[1..n] be two sorted (in increasing order) arrays, each containing n numbers. Design an O(log n)-time algorithm to find the median of all 2n elements in arrays A and B. Explain your answer and analyze the complexity. 連結: http://www.edu.tw/files/site_content/B0003/65%E6%BC%94%E7%AE%97%E6%B3%95.pdf 我的想法是抓A[n/2], B[n/2]出來比較，但細節不知道如何描述，有人有好的解法嗎?? 謝謝分享 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 122.127.222.204

推

gskman

01/21 11:00, , 1^F

01/21 11:00, 1^F

推

louis719

01/21 11:39, , 2^F

01/21 11:39, 2^F

→

louis719

01/21 11:40, , 3^F

01/21 11:40, 3^F