class Solution(object):

    # Op1: O(n log(n))
    def wiggleSort(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        s = sorted(nums)
        l, r = 0, len(s) - 1
        i = 0
        while i < len(nums):
            nums[i] = s[l]
            l += 1
            i += 2
        j = 1
        while j < len(nums):
            nums[j] = s[r]
            r -= 1
            j += 2

    def wiggleSort2(self, nums):
        for i in range(len(nums)):
            a = nums[i - 1]
            if (i % 2 == 1) == (a > nums[i]):
                nums[i - 1] = nums[i]
                nums[i] = a

    def wiggleSort3(self, nums):
        for i in range(1, len(nums)):
            if (i & 1) == (nums[i - 1] > nums[i]):
                nums[i - 1], nums[i] = nums[i], nums[i - 1]

    def wiggleSort4(self, nums):
        n = len(nums)
        for i in range(n - 1):
            if (i % 2 == 0 and nums[i] > nums[i + 1]) or \
                (i % 2 == 1 and nums[i] < nums[i + 1]):
                nums[i], nums[i + 1] = nums[i + 1], nums[i]
                print(nums[i], nums[i + 1], nums)


nums = [3, 5, 2, 1, 6, 4]
#nums = [1, 2, 3, 4, 5, 6]
test = Solution()
test.wiggleSort3(nums)
print(nums)
