324.Wiggle Sort II

Tags: [sort], [trick], [math]

Link: https://leetcode.com/problems/wiggle-sort-ii/\#/description

Given an unsorted arraynums, reorder it such thatnums[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: Sort

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

        sorted_nums = sorted(nums)
        num_of_elems_in_odd_position = len(sorted_nums[::2]) # here we think the first elem is in odd position

        left = sorted_nums[:num_of_elems_in_odd_position]
        left.reverse()
        right = sorted_nums[num_of_elems_in_odd_position:]
        right.reverse()

        result = []
        left_index = 0
        right_index = 0
        while left_index < len(left) and right_index < len(right):
            result.append(left[left_index])
            result.append(right[right_index])
            left_index += 1
            right_index += 1

        if left_index < len(left):
            result += left[left_index:]
        if right_index < len(right):
            result += right[right_index:]

        # In Python, once we assign a new value to nums, such as nums = [], 
        # the nums will no longer bind to the original pass-in nums.
        # So if we want to modify the original pass-in nums, we should use below way.
        for i in xrange(len(nums)):
            nums[i] = result[i]

Revelation:

• When we break the size of left sublist is not len(nums) / 2, it should be len(nums[::2]). For example, nums = [5, 3, 1, 2, 6, 7, 8, 5, 5], after sorted it, the nums = [1, 2, 3, 5, 5, 5, 6, 7, 8], len(nums) / 2 = 4, but len(nums[::2]) = 5. If the size of left sublist is 4, the final result will be [5, 3, 2, 1, 8, 7, 6, 5, 5], and if the size of left sublist is 5, the final result will be [5, 8, 5, 7, 3, 6, 2, 5, 1].
• The reason we need reverse the left part is that after sorting and split in the 'middle' of the list, we get left[small->big] and right[small->big], obviously we need to reverse the right sublist, but we also need to reverse the left sublist, because there exists duplicates, and after sorting the duplicates shared between left and right will be located in the middle of the nums, if we don't reverse left but only reverse right, the duplicates will be located in the right side of the left sublist, and the right side of the right sublist, so after merging, the duplicates will be together. So we also reverse left sublist, now left[big->small], and right[big->small], the duplicates shared between left and right, will located in the left side of left sublist, and the right side of right sublist.

Note:

• Time complexity = O(nlgn), n is the number of elements of the given array.
• Space complexity = O(n), n is the number of elements of the given array.

Clean and simplify code:

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

        nums.sort()
        num_of_elem_in_odd_position = len(nums[::2])
        nums[::2], nums[1::2] = nums[:num_of_elem_in_odd_position][::-1], nums[num_of_elem_in_odd_position:][::-1]

Follow-up: