# 摆动排序 II
给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。
你可以假设所有输入数组都可以得到满足题目要求的结果。
示例 1：
输入：nums = [1,5,1,1,6,4]
输出：[1,6,1,5,1,4]
解释：[1,4,1,5,1,6] 同样是符合题目要求的结果，可以被判题程序接受。
示例 2：
输入：nums = [1,3,2,2,3,1]
输出：[2,3,1,3,1,2]
提示：
1 <= nums.length <= 5 * 1040 <= nums[i] <= 5000- 题目数据保证，对于给定的输入
nums ，总能产生满足题目要求的结果
进阶：你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗？
以下错误的选项是？
## aop
### before
```cpp
#include
using namespace std;
```
### after
```cpp
```
## 答案
```cpp
class Solution
{
public:
void wiggleSort(vector &nums)
{
if (nums.size() <= 1)
return;
sort(nums.begin(), nums.end());
int len = nums.size(), k = 1, high = (len % 2) ? len - 1 : len - 2, mid = nums[len / 2];
vector ans(len, mid);
for (int i = len - 1; i >= 0 && nums[i] > mid; --i, k++)
ans[k] = nums[i];
for (int i = 0; i < len && nums[i] < mid; ++i, high--)
ans[high] = nums[i];
nums = ans;
}
};
```
## 选项
### A
```cpp
class Solution
{
public:
void wiggleSort(vector &nums)
{
vector tmp(nums);
sort(tmp.begin(), tmp.end(), greater());
int size = nums.size() / 2;
for (int i = 0; i < size; ++i)
nums[i * 2 + 1] = tmp[i];
for (int i = size; i < nums.size(); ++i)
nums[(i - size) * 2] = tmp[i];
}
};
```
### B
```cpp
class Solution
{
public:
void wiggleSort(vector &nums)
{
vector numsmin;
sort(nums.begin(), nums.end());
if (nums.size() % 2 == 0)
{
for (int i = nums.size() / 2 - 1; i >= 0; i--)
{
numsmin.push_back(nums[i]);
numsmin.push_back(nums[i + nums.size() / 2]);
}
nums = numsmin;
return;
}
for (int i = nums.size() / 2; i >= 1; i--)
{
numsmin.push_back(nums[i]);
numsmin.push_back(nums[i + nums.size() / 2]);
}
if (nums.size() % 2 != 0)
numsmin.push_back(nums[0]);
nums = numsmin;
return;
}
};
```
### C
```cpp
class Solution
{
public:
void wiggleSort(vector &nums)
{
int n = nums.size();
vector tmp(nums);
sort(tmp.begin(), tmp.end());
int mid = n / 2, end = n - 1;
if (n % 2 == 0)
mid--;
for (int i = 0; i < n; i++)
{
nums[i] = i % 2 == 0 ? tmp[mid--] : tmp[end--];
}
}
};
```