Day88 摆动排序 II

给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。

你可以假设所有输入数组都可以得到满足题目要求的结果。

324. 摆动排序 II - 力扣（LeetCode） (leetcode-cn.com)

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

示例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 ，总能产生满足题目要求的结果

Java解法

思路：

• 初步设想1：

  • 按位遍历，在当前位置查找比自身小或大的位置，放置右边，指针右移

  • 如果找不到，此时找后续位置大于（或小于）自己及自己-1位置的数放置其中

  • 失败用例 1,4,3,4,1,2,1,3,1,3,2,3,3 既找不到，也换不到

    public static void wiggleSort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        int len = nums.length;
        //数组规律： 小 大 小
        int curr = 0;
        int pre = curr + 1;
        boolean findBigger = true;
        while (curr < len - 1) {
            if (findBigger) {
                if (nums[curr] < nums[pre]) {
                    curr++;
                    pre = curr+1;
                    findBigger = false;
                } else {
                    while (pre < len) {
                        if (nums[curr] < nums[pre]) {
                            //交互pre 与curr+1的位置
                            int temp = nums[pre];
                            nums[pre] = nums[curr + 1];
                            nums[curr + 1] = temp;
                            pre= curr+1;
                            break;
                        } else {
                            pre++;
                        }
                    }
                    if (pre < len) {
                        //找到了
                        curr++;
                        pre = curr + 1;
                        findBigger = false;
                    } else {
                        //没找到， 将curr 与后面位置交换，当前位置找更大，说明curr-1 找更小，后面都更小，找一个不等的交互位置后进行当前操作
                        pre = curr + 1;
                        while (pre < len) {
                            if (nums[curr] > nums[pre]) {
                                //交换
                                int temp = nums[pre];
                                nums[pre] = nums[curr];
                                nums[curr] = temp;
                                pre = curr + 1;
                                break;
                            }else {
                                pre++;
                            }
                        }
                    }
                }
            } else {
                if (nums[curr] > nums[pre]) {
                    curr++;
                    pre = curr+1;
                    findBigger = true;
                } else {
                    while (pre < len) {
                        if (nums[curr] > nums[pre]) {
                            //交互pre 与curr+1的位置
                            int temp = nums[pre];
                            nums[pre] = nums[curr + 1];
                            nums[curr + 1] = temp;
                            pre= curr+1;
                            break;
                        } else {
                            pre++;
                        }
                    }
                    if (pre < len) {
                        //找到了
                        curr++;
                        pre = curr + 1;
                        findBigger = true;
                    } else {
                        //没找到， 将curr 与后面位置交换，当前位置找更大，说明curr-1 找更小，后面都更小，找一个不等的交互位置后进行当前操作
                        pre = curr + 1;
                        while (pre < len) {
                            if (nums[curr] > nums[pre]) {
                                //交换
                                int temp = nums[pre];
                                nums[pre] = nums[curr];
                                nums[curr] = temp;
                                pre = curr + 1;
                                break;
                            }else {
                                pre++;
                            }
                        }
                    }
                }
            }
        }
    
    }
    

• 设想2：

  • 数据的位置关系是中间大于两侧，方案是
    1. 数组排序
    2. 中点切半
    3. 间隔插入
  • 失败用例 [4,5,5,6] ：存在重复数据在最后间隔插入时导致重复
  • 修复：插入时使用倒序插入，big组与small组使用最大值开始插入

package sj.shimmer.algorithm.m4_2021;

import java.util.Arrays;

import sj.shimmer.algorithm.Utils;

/**
 * Created by SJ on 2021/4/25.
 */

class D88 {
    public static void main(String[] args) {
        int[] nums = new int[]{1,1,2,1,2,2,1};
        wiggleSort(nums);
        Utils.logArray(nums);
        nums = new int[]{1, 5, 1, 1, 6, 4};
        wiggleSort(nums);
        Utils.logArray(nums);

        nums = new int[]{1, 3, 2, 2, 3, 1};
        wiggleSort(nums);
        Utils.logArray(nums);
        nums = new int[]{5,5,5,4,4,4,4};
        wiggleSort(nums);
        Utils.logArray(nums);
        nums = new int[]{1,4,3,4,1,2,1,3,1,3,2,3,3};
        wiggleSort(nums);
        Utils.logArray(nums);
        nums = new int[]{4,5,5,6};
        wiggleSort(nums);
        Utils.logArray(nums);
    }

    public static void wiggleSort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        Arrays.sort(nums);
        int len = nums.length;
        int mid = (len+1)/2;
        int[] result = new int[len];
        System.arraycopy(nums, 0, result,0, len);
        int small =mid-1;
        int big = len-1;
        for (int i = 0; i < len; i++) {
            if (i%2==0) {
                nums[i] = result [small];
                small--;
            }else {
                nums[i] = result [big];
                big--;
            }
        }
    }
}

image

官方解

暂无：参考解： 324. 摆动排序 II 题解 - 力扣（LeetCode） (leetcode-cn.com)