Share my python code using Perfect Shuffle Algorithm


  • 2

    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)

  • 0

    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.


  • 0
    R

    can you explain more about the perfect shuffle?


Log in to reply
 

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