推 xcycl:原 po 是問想做到 space 複雜度為 O(1), 不是 time ... 11/17 21:43
推 ykjiang:我也看走眼了 :p 11/17 23:23
推 ledia:他的意思是 in place permutation ? 11/18 01:09
推 b6s:唔，大概是我弄錯了，可這不是 swap 頭尾成對的偶數項就好？ 11/18 04:13
推 b6s:btw, 我所謂頭尾成對偶數項，尾巴那隻是倒數的偶數項。 11/18 04:21
利用多次 swap，有一個 space O(1), time O(N^2) 的方法，
過程舉例如下：
0 (1 2) (3 4) (5 6) (7 8) 9
0 2 (1 4) (3 6) (5 8) 7 9
0 2 4 (1 6) (3 8) 5 7 9
0 2 4 6 (1 8) 3 5 7 9
0 2 4 6 8 1 3 5 7 9
每個 pass 都把括號內的數對 swap...
這其實是以 in place 法求轉置矩陣的一個特例，
換句話說，它是求 N by 2 矩陣的轉置（transpose）
有興趣的人，可以幫忙推廣成適用於 n by m 矩陣
的轉置矩陣。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.59.14.146
※ 編輯: ykjiang 來自: 61.59.14.146 (11/18 12:12)
推 drkkimo:好方法 11/18 20:56
推 ykjiang:從這個方法出發，我幾乎可以確定 space O(1), time O(N) 11/19 02:09
→ ykjiang:的方法存在，有興趣的人可以推推看 :) 11/19 02:10
推 b6s:雖然 swap 的順序不同，但我想到的跟這一樣，推～ 11/20 01:19
→ b6s:BTW, 這個問題應該可以視為 bipartite，所以 space O(1) 應該 11/20 01:19
→ b6s:可是同時要 time O(N) 就不知道了，感覺上好像頂多 O(NlogN) 11/20 01:20