LeetCode_排序_中等_324.摆动排序 II-蒲公英云

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

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]--;
    }
}