Re: [問題] array shuffle
※ 引述《foo.bbs@bbs.ntu.edu.tw (bar)》之銘言：
: ==> FRAXIS.bbs@ptt.cc (喔喔) 提到:
: > 這是在網路上看到的一個面試問題，不過我一直想不出來解法。
: > 給你一個長度為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
推
07/20 11:14, , 1F
07/20 11:14, 1F
→
07/20 11:14, , 2F
07/20 11:14, 2F
→
07/20 11:14, , 3F
07/20 11:14, 3F
→
07/20 11:15, , 4F
07/20 11:15, 4F
→
07/20 11:16, , 5F
07/20 11:16, 5F
推
07/20 11:24, , 6F
07/20 11:24, 6F
→
07/20 11:25, , 7F
07/20 11:25, 7F
討論串 (同標題文章)
Programming 近期熱門文章
PTT數位生活區 即時熱門文章
