324. Wiggle Sort II

做题历程：

1. 2016/Oct/20，这是第一次做这道题。没有解出

本题跟280. Wiggle Sort还是有比较大的区别的，所以没有顺利解出，一个关键点就是不允许相等，所以那种不停地swap的模式可能无法奏效。

本题我没有选择最优方法，我觉得那种比较难，会到Hard的范畴。。而且至少是中等水平的Hard

本题思路：

1. sort给定数组，然后取一下中点，交叉插入
2. 这种方法在[4, 5, 5, 6]会失效。所以一定要一种方法确保小数最大的，大数最小的不能接触
3. 所以需要改进一点，就是倒序就可以了

代码如下：

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        vector<int> tmp = nums;
        sort(tmp.begin(), tmp.end());
        int small_idx = (nums.size() - 1) / 2;
        int large_idx = nums.size() - 1;

        for (int i = 0; i < nums.size(); ++i) {
            if (i % 2 == 0) {
                nums[i] = tmp[small_idx--];
            }
            else {
                nums[i] = tmp[large_idx--];
            }
        }
    }
};