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)
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
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.
Interesting ... I can't view the article other than the abstract. Is wikipedia wrong then? https://en.wikipedia.org/wiki/Quicksort#Space_complexity
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.