324. Wiggle Sort II

Leetcode Sort

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

Example 1:

Input: nums = [1, 5, 1, 1, 6, 4]
Output: One possible answer is [1, 4, 1, 5, 1, 6].

Example 2:

Input: nums = [1, 3, 2, 2, 3, 1]
Output: 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?

分析

这道题目与280. Wiggle Sort相比，在条件中去掉了等号，把小于等于改成了小于，把大于等于改成了大于。但是这一改原来的方法彻底不管用了。

最直接的方法是将数组排序，然后将数移动到正确位置。

public void wiggleSort(int[] nums) {
    int n = nums.length, m = (n + 1) >> 1;
    int[] copy = nums.clone();
    Arrays.sort(copy);
    for (int i = m - 1, j = 0; i >= 0; i--, j += 2) nums[j] = copy[i];
    for (int i = n - 1, j = 1; i >= m; i--, j += 2) nums[j] = copy[i];
}