324. Wiggle Sort II

难度: Medium

题目描述

Given an integer array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....

You may assume the input array always has a valid answer.

 

Example 1:

Input: nums = [1,5,1,1,6,4]
Output: [1,6,1,5,1,4]
Explanation: [1,4,1,5,1,6] is also accepted.

Example 2:

Input: nums = [1,3,2,2,3,1]
Output: [2,3,1,3,1,2]

 

Constraints:

• 1 <= nums.length <= 5 * 104
• 0 <= nums[i] <= 5000
• It is guaranteed that there will be an answer for the given input nums.

 

Follow Up: Can you do it in O(n) time and/or in-place with O(1) extra space?

解题思路

代码实现

解决方案

java

class Solution {
    /**
     * 对数组进行摆动排序，使得数组中的元素满足arr[0] <= arr[1] >= arr[2] <= arr[3]...
     * 此方法通过计数排序的思想实现，适用于一定条件下的整数排序
     * 
     * @param arr 待排序的整数数组
     */
    public void wiggleSort(int[] arr) {
        // 判断数组是否为空或只有一个元素，如果是，不需要排序，直接返回
        if (arr == null || arr.length <= 1) {
            return;
        }

        // 初始化变量，max用于记录数组中的最大值，hasNegative用于标记数组中是否有负数
        int max = Integer.MIN_VALUE;

        // 单次遍历检测负数并找到最大值
        for (int num : arr) {
            // 如果当前数字大于已知的最大值，更新最大值
            if (num > max) {
                max = num;
            }
        }

        // 执行计数排序，这是基于最大值的排序算法，适合一定条件下的整数排序
        countingSort(arr, max);
        // 创建一个临时数组buf用于重新排列元素
        int[] buf = new int[arr.length];
        // 根据数组长度的奇偶性确定中间位置的索引
        int lelf = buf.length % 2 == 0 ? buf.length / 2 : buf.length / 2 + 1;

        // 重新排列数组元素，以实现摆动排序的要求
        int index = 0;
        for (int i = lelf - 1, j = arr.length - 1; i > -1 && j >= lelf; i--, j--) {
            buf[index] = arr[i];
            buf[++index] = arr[j];
            index++;
        }
        // 如果数组长度为奇数，处理中间剩余的元素
        if (arr.length % 2 == 1) {
            buf[arr.length - 1] = arr[0];
        }

        // 将重新排列后的元素复制回原数组
        System.arraycopy(buf, 0, arr, 0, arr.length);
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private void countingSort(int[] arr, int max) {
        // 检查输入数组是否为空
        if (arr == null || arr.length == 0) {
            throw new IllegalArgumentException("输入数组不能为空");
        }

        // 验证数组中是否存在负数或 max 参数是否合理
        for (int num : arr) {
            if (num < 0) {
                throw new IllegalArgumentException("数组中包含负数，计数排序不支持负数");
            }
            if (num > max) {
                throw new IllegalArgumentException("数组中存在大于 max 的值，max 参数不合理");
            }
        }

        // 创建计数数组
        int[] countArray = new int[max + 1];

        // 统计每个整数出现的次数
        for (int num : arr) {
            countArray[num]++;
        }

        // 计算累积计数
        for (int i = 1; i < countArray.length; i++) {
            countArray[i] += countArray[i - 1];
        }

        // 直接在原数组上进行排序
        int[] temp = arr.clone(); // 使用临时数组保存原始数据
        for (int i = temp.length - 1; i >= 0; i--) {
            int num = temp[i];
            arr[countArray[num] - 1] = num;
            countArray[num]--;
        }

    }

}