==> [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 -- ☆ [Origin:椰林风情] [From: 220-132-95-228.hinet-ip.hin] [Login: **] [Post: 1]