Share my python code using Perfect Shuffle Algorithm

• This is not a O(n) solution like the other posts. I just want to give another way to solve this problem.

First sort the array, then use perfect shuffle algorithm to rerange it.

Take `[3, 1, 4, 8, 2, 9]` as axample, first sort it to `[1, 2, 3, 4, 8, 9]`, then shuffle it to `[1, 4, 2, 8, 3, 9]`.

``````class Solution(object):
def reverse(self, start, end):
low, high = start, end
while low < high:
self.nums[low], self.nums[high] = self.nums[high], self.nums[low]
low += 1
high -= 1

def getK(self, n):
k, square = 1, 3
while square - 1 <= 2 * n:
k += 1
square *= 3
return k - 1

def shuffle(self, start, end):
n = (end - start + 1) / 2

k = self.getK(n)
m = (3 ** k - 1) / 2
if m != n:
self.reverse(start + m, start + n - 1)
self.reverse(start + n, start + n + m - 1)
self.reverse(start + m, start + n + m - 1)

for k in xrange(1, k + 1):
i = cursor = 3 ** (k - 1)
pre, visited = self.nums[i + start - 1], False
while not (i == cursor and visited):
i = (2 * i) % (2 * m + 1)
self.nums[i + start - 1], pre = pre, self.nums[i + start - 1]

if not visited:
visited = True

if n != m:
self.shuffle(start + 2 * m, end)

def wiggleSort(self, nums):
length = len(nums)
if length < 2:
return

nums.sort()

start, end = 1, length - 1
if not length & 1:
end -= 1

self.nums = nums
self.shuffle(start, end)``````

• Why vote down? This is may not be the best solution like other posts with O(n), but it gives out another way to solve this problem.

• can you explain more about the perfect shuffle?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.