O(nlogn) Perfect Shuffle solution


  • 2

    Refer to this paper: http://arxiv.org/pdf/0805.1598.pdf

    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

    Nice in place solution~


  • 0
    A

    Is sorting necessarily O(1) in space? Quick sort is O(n) space and I can't think of anything that is better that also achieves O(nlogn) time


  • 0

    It can be. For quicksort, see here.
    For mergesort, see here

    Therefore it depends on the library implement. For the purpose of this problem I think you may assume the sort used O(1) extra space.


  • 0
    A

    Interesting ... I can't view the article other than the abstract. Is wikipedia wrong then? https://en.wikipedia.org/wiki/Quicksort#Space_complexity


  • 0

    Maybe the wikipedia writer just considered the classical variants of these sorting algorithms.
    Then again, you may change the article yourself.
    Anyway, for this problem sort is not always needed.


Log in to reply
 

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