Re: [問題] array shuffle
==> 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
--
☆ [Origin:椰林風情] [From: 220-132-95-228.hinet-ip.hin] [Login: **] [Post: 1]
推
07/19 11:43, , 1F
07/19 11:43, 1F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 4 之 9 篇)：
Programming 近期熱門文章
PTT數位生活區 即時熱門文章
