题目描述

给定一个无序数组nums，请调整它的顺序，使得nums[0] < nums[1] > nums[2] < nums[3] ...。

注意： 数据保证一定存在答案。

进一步： 能否只使用 $O(n)$ 的时间，以及额外 $O(1)$ 的空间。

样例1

输入：nums = [1, 5, 1, 1, 6, 4]
输出：一种可能的答案是 [1, 4, 1, 5, 1, 6].

样例2

输入：nums = [1, 3, 2, 2, 3, 1]
输出：一种可能的答案是 [2, 3, 1, 3, 1, 2].

算法

(快速选择+三数排序) $O(n)$

首先我们需要先了解一下快速选择算法，它可以在期望 $O(1)$ 的时间复杂度内求出第 $k$ 大数。
我们先用快速选择算法求出中位数mid，C++中可以调用 nth_element()函数。

将所有数分成三种：小于mid的数、等于mid的数和大于mid的数。
然后对数组排序，使得大于mid的数在最前面，等于mid的数在中间，小于mid的数在最后面。
这一步可以直接利用三数排序，三数排序算法可以参考LeetCode 75. Sort Colors。

然后我们将排好序的数组重排，将前半段依次放到奇数位置上，将后半段依次放到偶数位置上。此时就会有：
nums[0] < nums[1] > nums[2] < nums[3] ...

这一步重排我们可以在三数排序时做，只需在排序时做一个数组下标映射即可：
i => (1 + 2 * i) % (n | 1)
该映射可以将数组前一半映射到奇数位置上，数组后一半映射到偶数位置上。

时间复杂度分析：快速选择算法的期望运行时间是 $O(n)$，额外空间是 $O(logn)$(算法需要递归，期望递归 $logn$ 层)。三数排序算法的时间复杂度是 $O(n)$，额外空间复杂度是 $O(1)$。所以总时间复杂度是 $O(n)$，额外空间的复杂度是 $O(logn)$。题目中要求只使用额外 $O(1)$ 的空间，目前还没想到比较好的做法。有想法的同学可以在评论区交流 ^^。

C++ 代码

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        int n = nums.size();
        auto midptr = nums.begin() + n / 2;
        nth_element(nums.begin(), midptr, nums.end());
        int mid = *midptr;

        #define A(i) nums[(1 + 2 * i) % (n | 1)]

        int i = 0, j = 0, k = n - 1;
        while (j <= k)
            if (A(j) > mid)
                swap(A(i ++ ), A(j ++ ));
            else if (A(j) < mid)
                swap(A(j), A(k -- ));
            else
                j ++ ;
    }
};