Wiggle Sort

题目描述

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].

解题方法

因为有一个等号，所以比II的条件宽松很多。当数组中有重复数字存在的情况时，也容易满足题目的要求。

先排序

先排序，这样数组就是sorted一直递增的，然后从第3个开始，将

• 3, 2
• 5, 4
• 7, 6
• 。。。。 调换位置，就可以完成了。

time: O(nlogn)

直接greedy遍历

因为可以相等所以，直接遍历这个数组。

• 当i为odd, nums[i] >= nums[i-1]
• 当i为even, nums[i] <= nums[i-1]

Solution

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

        for i in range(1, length):
            if ((i % 2) and nums[i] < nums[i-1]) or (not (i % 2) and nums[i] > nums[i-1]):
                nums[i-1], nums[i] = nums[i], nums[i-1]

Reference

• wiggle sort