solution.md

# 摆动排序 II
<p>给你一个整数数组 <code>nums</code>，将它重新排列成 <code>nums[0] < nums[1] > nums[2] < nums[3]...</code> 的顺序。</p>

<p>你可以假设所有输入数组都可以得到满足题目要求的结果。</p>

<p> </p>

<p><strong>示例 1：</strong></p>

<pre>
<strong>输入：</strong>nums = [1,5,1,1,6,4]
<strong>输出：</strong>[1,6,1,5,1,4]
<strong>解释：</strong>[1,4,1,5,1,6] 同样是符合题目要求的结果，可以被判题程序接受。
</pre>

<p><strong>示例 2：</strong></p>

<pre>
<strong>输入：</strong>nums = [1,3,2,2,3,1]
<strong>输出：</strong>[2,3,1,3,1,2]
</pre>

<p> </p>

<p><strong>提示：</strong></p>

<ul>
	<li><code>1 <= nums.length <= 5 * 10<sup>4</sup></code></li>
	<li><code>0 <= nums[i] <= 5000</code></li>
	<li>题目数据保证，对于给定的输入 <code>nums</code> ，总能产生满足题目要求的结果</li>
</ul>

<p> </p>

<p><strong>进阶：</strong>你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗？</p>

<p>以下错误的选项是？</p>
## aop
### before
```cpp
#include <bits/stdc++.h>
using namespace std;

```
### after
```cpp

```

## 答案
```cpp
class Solution
{
public:
    void wiggleSort(vector<int> &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<int> 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<int> &nums)
    {
        vector<int> tmp(nums);
        sort(tmp.begin(), tmp.end(), greater<int>());

        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<int> &nums)
    {
        vector<int> 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<int> &nums)
    {
        int n = nums.size();
        vector<int> 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--];
        }
    }
};
```