LeetCode_排序_中等_324.摆动排序 II

柔情只为你懂 2023-10-06 18:53 1阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个整数数组 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 \* 104  
0 <= nums\[i\] <= 5000  
题目数据保证，对于给定的输入 nums ，总能产生满足题目要求的结果

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/wiggle-sort-ii

## 2.思路 ##

（1）排序+穿插  
通过分析题目可知，在重新排列后的数组 nums 中，下标为奇数的元素值都大于与其相邻的元素值（或者说下标为偶数的元素值都小于与其相邻的元素值），所以可以考虑先排序再穿插的思路，其具体步骤如下：  
① 先将数组 nums 克隆一份赋值给 assist，并且对数组 assist 进行升序排序；  
② 将数组 assist 中的较大值（即assist后半部分的整数）赋值到数组 nums 中下标为奇数的位置；  
③ 将数组 assist 中的较小值（即assist前半部分的整数）赋值到数组 nums 中下标为偶数的位置；

（2）桶排序+穿插

## 3.代码实现（Java） ##

//思路1————排序+穿插
    public void wiggleSort(int[] nums) {
        
        //将数组nums克隆一份赋值给assist
        int[] assist = nums.clone();
        //对数组assist进行排序
        Arrays.sort(assist);
        int aLen = assist.length;
        int nLen = nums.length;
        //将排序后的数组assist中的整数分2部分穿插到数组nums中
        //将数组assist中的较大值赋值到数组nums中下标为奇数的位置
        for (int i = 1; i < nLen; i += 2) {
        
            aLen--;
            nums[i] = assist[aLen];
        }
        //将数组assist中的较小值赋值到数组nums中下标为偶数的位置
        for (int i = 0; i < nLen; i += 2) {
        
            aLen--;
            nums[i] = assist[aLen];
        }
    }

//思路2————桶排序+穿插
    public void wiggleSort(int[] nums) {
        
        //nums:[1,5,1,1,6,4]
        int maxNum = 0;
        //找出数组 nums 中的最大值，maxNum = 6
        for (int num : nums) {
        
            maxNum = Math.max(num, maxNum);
        }
        int[] bucket = new int[maxNum + 1];
        //bucket:[0, 3, 0, 0, 1, 1, 1]
        for (int num : nums) {
        
            bucket[num]++;
        }
        int length = nums.length;
        int k = maxNum;
        //将数组 bucket 中较大的元素插入到 nums 中下标是奇数的位置
        for (int i = 1; i < length; i += 2) {
        
            while (bucket[k] == 0) {
        
                k--;
            }
            nums[i] = k;
            bucket[k]--;
        }
        //将数组 bucket 中较小的元素插入到 nums 中下标是偶数的位置
        for (int i = 0; i < length; i += 2) {
        
            while (bucket[k] == 0) {
        
                k--;
            }
            nums[i] = k;
            bucket[k]--;
        }
    }