看板 [ Grad-ProbAsk ]
討論串[理工] 97東華資結
共 3 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[理工] 97東華資結
推噓4(4推 0噓 2→)留言6則，0人參與, 最新作者InitialShuk (Shuk)時間15年前 (2009/04/09 15:47), 編輯資訊
1
0
0
內容預覽:
X Y為兩個sorted好的 含n element的array. 請用O(logN)的algo 找出 X聯集Y之中間值. 目前只想到O(N) ...... --. --. ※ 發信站: 批踢踢實業坊(ptt.cc). ◆ From: 118.160.161.72. ※ 編輯: InitialShuk
#2
Re: [理工] 97東華資結
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者fish0835 (以無用為大用)時間15年前 (2009/04/09 20:21), 編輯資訊
1
0
0
內容預覽:
假設X,Y是由小至大排好的array. steps:. 1.把X,Y的中間值a,b拿來比較. 2.不失其一般性的假設 a < b ，則將X的左半部與Y的右半部刪去。. 3.重復 1~2 直到找到中間值. time complexity:. 每次皆刪去一半的不可能之情況，所以時間函數為.... T(n
(還有3個字)
#3
Re: [理工] 97東華資結
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者swon (囧興囧九囧rz)時間15年前 (2009/04/11 02:13), 編輯資訊
0
0
0
內容預覽:
想法是二分搜尋法~. 不過要搜尋的對象有些條件. 就 X 中的元素 X[k] 而言. 我們會發現在 X Array 當中有 k 個元素會小於等於 X[k]. 現在我們要找到 X Y Array 的中位數. (X Y 中共有 n 個數小於等於他們的中位數). 所以我們需要確認在 Y 中是不是恰好有 (
(還有469個字)
首頁
上一頁
1
下一頁
尾頁