2022-06-28 「324. 摆动排序 II」

今日中等题：https://leetcode.cn/problems/wiggle-sort-ii/

今天的题目很有意思，看着很简单，我第一眼觉得不就是排个序，再插入的事儿嘛，然后做题的时候被啪啪打脸，卡在48/52的通过率上，仔细看了一眼测试用例才发现，我的整体思路没错：

1. 应该先复制一个数组出来，题目内的数组是nums，复制出来的叫copy，然后对copy排序，让它变成非降序（可能有重复的数字）；
2. 错在我想的双指针是nums[2 * i] = copy[i]; nums[2 * i + 1] = copy[i + (len + 1) / 2];

这样会导致一种什么情况？
[4,5,5,6] 应该排成[5,6,4,5]，但是我排完还是[4,5,5,6] ，详见下图：

那么换个思路，把左指针的从0开始向右移动，改成从中间开始向左移动，就能避开左侧最大值和右侧最小值正好相邻且相等的问题了～

看下代码：

class Solution {
    public void wiggleSort(int[] nums) {
        Arrays.sort(nums);
        int tail = nums.length - 1;
        int head = tail / 2;
        int[] ans = nums.clone(); 

        for (int i = 0; i < nums.length; i++) {
            if (i % 2 == 0) {
                nums[i] = ans[head];
                head--;
            }           
            else {
                nums[i] = ans[tail];
                tail--;
            }
        }        
    }
}