280.Wiggle Sort

Tags: [sort], [reverse], [trick]

Com: {g}

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

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

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

Solution: Sort, Reverse

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:
            return

        # make the num of elements in right is less than or equal to left.
        # make the elements in right is greater then the elements in left.
        # so after revering the right, we can insert the elements of right between the elements of left.
        nums.sort()
        left = nums[:len(nums) / 2 + 1]
        right = nums[len(nums) / 2 + 1:]
        right.reverse()

        left_index = 0
        right_index = 0
        index = 0
        is_left_turn = True
        while left_index < len(left) and right_index < len(right):
            if is_left_turn:
                nums[index] = left[left_index]
                left_index += 1
            else:
                nums[index] = right[right_index]
                right_index += 1

            is_left_turn = not is_left_turn
            index += 1

        while left_index < len(left):
            nums[index] = left[left_index]
            left_index += 1
            index += 1
        while right_index < len(right):
            nums[index] = right[right_index]
            right_index += 1
            index += 1

Revelation:

• Always make the num of elements of right is less than or equal to the num of elements of left. So that we can insert the elements of right between the elements of left, and after sorting, all elements of right are greater than or equal to the elements of left.

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.

Time Limited Exceeded: Truly In Place

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:
            return

        nums.sort()
        self.reverse(nums, len(nums) / 2 + 1, len(nums) - 1)
        left = 0
        right = len(nums) / 2 + 1

        while right < len(nums):
            right_elem = nums[right]

            # shifting left elements to right by one slot.
            for i in xrange(right, left + 1, -1):
                nums[i] = nums[i - 1]

            nums[left + 1] = right_elem
            left += 2
            right += 1

    def reverse(self, arr, start, end):
        while start < end:
            arr[start], arr[end] = arr[end], arr[start]
            start += 1
            end -= 1

Note:

• Time complexity = O(n^2), n is the number of elements of the given nums.
• Space complexity = O(1).