324. Wiggle Sort II | 324. 摆动排序 II（降序穿插）

ゞ浴缸里的玫瑰 2022-10-20 00:55 112阅读 0赞

## 题目 ##

[https://leetcode.com/problems/wiggle-sort-ii/submissions/][https_leetcode.com_problems_wiggle-sort-ii_submissions]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

## 题解 ##

没有一次想到正确的方法，是在 WA 的测试用例的提示下，一点一点修正，才通过的。

##### 思路 #####

降序穿插，并且需要避免数组中间位置可能有的重复。看图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]

class Solution { 
        public void wiggleSort(int[] nums) { 
            // sort
            int[] sorted = new int[nums.length];
            Arrays.sort(nums);
            System.arraycopy(nums, 0, sorted, 0, nums.length);
            // merge
            int i = nums.length - 1;
            int L = (nums.length - 1) / 2;
            int R = nums.length - 1;
            while (i >= 0) { 
                nums[i--] = sorted[L--];
                if (i < 0) break;
                nums[i--] = sorted[R--];
            }
            // reverse
            for (int j = 0; j < nums.length / 2; j++) { 
                int t = nums[j];
                nums[j] = nums[nums.length - j - 1];
                nums[nums.length - j - 1] = t;
            }
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

[https_leetcode.com_problems_wiggle-sort-ii_submissions]: https://leetcode.com/problems/wiggle-sort-ii/submissions/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20221004/1434240d655e4d59b1c32cce2bb3d79d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]: /images/20221004/41f470b1a8c841d5ad07f5d408349e07.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221004/bb34eca4de0447c49ce0518667294edf.png