→ P568912:第一個我覺得可以把一個array sorting好(eg:X array) 02/13 17:35
→ P568912:然後對Ｙ array的每個數值用binary search找出跟他最近的 02/13 17:36
→ P568912:值 然後再去比較每個pair的最小值就應該可以了 02/13 17:37
→ P568912:第二題的意思應該就是quick sort的partition吧 02/13 17:38
→ bjk:題目沒說K擺在哪裡 02/13 17:51
→ bjk:且直接代的話好像沒辦法解決K要擺哪裡 02/13 17:52
推 kyodaisuki:一樓一定是大神! 02/13 18:00
推 lexa:第二題就每個元素跟K比大小 小的放K前大的放K後 O(n)就好了吧 02/13 18:55
→ lexa:想要看array裏面K放在哪也只要O(n)就好啦 02/13 18:56
推 yyc1217:第二題我想是從頭、尾各取一個跟k比較，分三種情況 02/13 19:06
→ yyc1217:一大一小，則小的放左邊那個位置，大的放右邊那個位置 02/13 19:07
→ yyc1217:然後取從左算來跟從右算來第二個，換下一輪 02/13 19:08
→ yyc1217:兩小，則原來在左邊的不動，大的跟左邊算來第二個交換 02/13 19:09
→ yyc1217:跟右邊算來第二個，一起換下一輪。兩小則反過來 02/13 19:09
→ yyc1217:大致上的想法是這樣啦 雖然是交卷後才想到的...QQ 02/13 19:11
推 llll5566:聽說演算法有三題 有人記得第三題嗎@@ 想知道 02/13 19:29
推 aiweisen:第三題好像是圖論的 02/13 22:47
推 ted0:第三題很像是MST 02/14 00:13
推 kitfretas:第三題有三個小題 02/14 00:40
→ kitfretas:1.寫出任意一個MST的演算法及其時間複雜度 02/14 00:41
→ kitfretas:2.在一Graph中，若減少不在MST中的edge之weight值，請寫 02/14 00:41
→ kitfretas:出一個O(|V|)的演算法來決定新的MST 02/14 00:42
→ kitfretas:3.在一Graph中，若加入一個vertex與edge，要花多久時間 02/14 00:43
→ kitfretas:才能決定新的MST 02/14 00:43
→ kitfretas:題目大概是這樣，有記錯或漏掉的條件再請各位補齊吧@@ 02/14 00:44