Re: [問題] array shuffle

[xcycl (XOO)]

※ 引述《[e-mail] (bar)》之銘言：
: ==> [e-mail] (喔喔) 提到:
: > 這是在網路上看到的一個面試問題，不過我一直想不出來解法。
: > 給你一個長度為2n的陣列，其中元素為a1, a2, ..., an, b1, b2, ..., bn
: > 寫一個程式把這個陣列轉換成a1, b1, a2, b2, ..., an, bn
: > 時間限制是O(n)，空間限制是O(1)。
: > 我嘗試用in-place rearrangement的方法去做，但是沒辦法成功。
: > 有什麼好的辦法嘛？
: Method 1: Move to a new array
:           Time complexity: O(n) + space complexity: O(n)
: Method 2: For even number n
:           divide the array into 4 quaters, swap the 2nd and the 3rd quaters
:           Re-divide the swapped array into 2 halfs,
:           recursively do the swap for the first half and the 2nd half.
:           Complexity: O(nlogn) swap.
: Method 3: tmp <- a <- b <- c <- d <- ...... <- alpha <- beta <- gama <- tmp
:           Similar to method 1, requiring a derived mathematical formula to
:           decide the next position to move.
:           Time complexity:  n-1 moves (first and last elements being steady)
:           Space complexity: 1 element space for tmp
方法三可以說明一下嗎 ?

如果是將 permutation 做 cycle decomposition 時需要不止 O(1) 的空間,
還是有不作 cycle decomposition 的方法, 就可以算出來？

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.134.69.245
推 ephesians:我不懂為什麼你說cycle decomposition
→ ephesians:需要不只O(1)的空間?
→ ephesians:其實每個群互不影響,我可以用一個temp
→ ephesians:先做完第一群的輪調,再做第二群的輪調,
→ ephesians:...依序做完,空間可使用那固定少少的量
推 ephesians:抱歉我忘了我早想到為什麼不止O(1),
→ ephesians:請跳過上述問題