Shuffle an array
January 10th, 2010
No comments
Given an array a1, a2, a3, … an, b1, b2, b3… bn, convert it to an array a1,b2,a 2,b2,a3,b3….an,bn in O(1) space and O(n) time.
The current algorithm I came up with is O(1) space but O(n^2) running time.
I think it should have some property to make a transformation chain from the original array to the converted one like ai1->bi2->ai3-> bi4 -> …. -> ai1.