Wiggle Sort II

这题的follow up实在太难，没想出来，就贴一个简单的做法。首先先贴一下题目：

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?

这题的题意是要组成一个顺序交叉排列的数组，小大小大。。。这种。最简单的思路就是我们进行一次排序，然后从小的一半取一个数，然后从大的一半再取一个数，这样取完肯定能保证小的大的的顺序性，编码也比较简单：

void wiggleSort(vector<int>& nums) {
    if (nums.size() <= 1) {
        return;
    }
    vector<int> tmp = nums;
    std::sort(tmp.begin(), tmp.end());
    int mid = (nums.size()  - 1) / 2;
    int tail = nums.size() - 1;
    for (int i = 0; i < nums.size(); i += 2) {
        nums[i] = tmp[mid];
        if (tail != (nums.size() - 1) / 2) {
            nums[i + 1] = tmp[tail];
        }
        --mid; --tail;
    }
}