Wiggle Sort

Posted on | Edited on | | Views:

280. Wiggle Sort

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

将数组in-place进行wiggle排序. Wiggle排序的意思是, nums[0] <= nums[1] >= nums[2] <= nums[3]....

举个例子: [3,5,2,1,6,4]一种可能的Wiggle排序是[3,5,1,6,2,4]

思路 Thoughts

先将原来的数组排序, 然后一头一尾重新组合, 就是Wiggle排序了.
比如说 [1, 2, 3, 4, 5, 6, 7]. 这个数组的Wiggle排序就是[1, 7, 2, 6, 3, 5, 4]. 由于题目要求是in-place所以, 我们需要额外的空间去储存这个排序.

First sort this array, then construct the new array with one element from the front and one element from the back. For example, [1, 2, 3, 4, 5, 6, 7], the new array should be [1, 7, 2, 6, 3, 5 , 4]. Since the requirement is in-place modification, we need extra constent space to store the sorted array.

Code

1
2
3
4
5
6
7
8
9
10
11
12
def wiggleSort(nums):
    copy = sorted(nums)
    left = 0
    right = len(nums) - 1

    for i in range(len(nums) - 1):
        if i % 2 == 0:
            nums[i] = copy[left]
            left += 1
        else:
            nums[i] = copy[right]
            right -= 1

时间复杂度 Time Complexity

$O(nlogn)$

EOF