324. Wiggle Sort II

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....

Example:

1. Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
2. Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].

Note:

You may assume all input has valid answer.

Follow-Up:

Can you do it in $O(n)$ time and/or in-place with $O(1)$ extra space?

Solution: O(n) space

class Solution(object):
    def wiggleSort(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        nums.sort()
        half = len(nums) / 2
        if len(nums) % 2 == 1:
            nums[half], nums[-1] = nums[-1], nums[half]

        idx = half * 2 - 1
        for small, large in zip(nums[:half], nums[half:]):
            nums[idx] = large
            nums[idx - 1] = small
            idx -= 2

Lessons:

• Move median to tail if size is odd.
• Put large pair before small pair to avoid situation like [3, 4, 4, 5].
• nums[:half] makes a copy of slice.