作者xcycl (XOO)
看板Programming
标题Re: [问题] array shuffle
时间Fri Jul 20 00:18:32 2007
※ 引述《[email protected] (bar)》之铭言：
: ==> [email protected] (喔喔) 提到:
: > 这是在网路上看到的一个面试问题，不过我一直想不出来解法。
: > 给你一个长度为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
1F：推 ephesians:我不懂为什麽你说cycle decomposition 59.112.231.111 07/20 11:14
2F：→ ephesians:需要不只O(1)的空间? 59.112.231.111 07/20 11:14
3F：→ ephesians:其实每个群互不影响,我可以用一个temp 59.112.231.111 07/20 11:14
4F：→ ephesians:先做完第一群的轮调,再做第二群的轮调, 59.112.231.111 07/20 11:15
5F：→ ephesians:...依序做完,空间可使用那固定少少的量 59.112.231.111 07/20 11:16
6F：推 ephesians:抱歉我忘了我早想到为什麽不止O(1), 59.112.231.111 07/20 11:24
7F：→ ephesians:请跳过上述问题 59.112.231.111 07/20 11:25