题目描述补充

摆动排序问题 II 是一个常见的算法问题，要求你将一个数组重新排列，使得数组符合摆动的条件，即 nums[0] < nums[1] > nums[2] < nums[3]... 的形式，同时要求所有可能的摆动序列中，字典序最小的那个。如果数组无法被重新排列以满足摆动条件，则返回一个空数组。

示例

输入: [1, 5, 1, 1, 6, 4]

输出: [1, 6, 1, 5, 1, 4]

解释: [1, 4, 1, 5, 1, 6] 同样是有效的摆动序列，但 [1, 6, 1, 5, 1, 4] 是字典序最小的摆动序列。

解题思路

1. 排序：首先对数组进行排序。
2. 选择：使用两个指针分别指向排序后数组的开始和中间（或末尾），交替地从两端选择元素填充到结果数组中，以保持摆动序列的上升和下降。
3. 处理特殊情况：如果原数组全部相同，则无法形成摆动序列，返回空数组。

PHP 代码示例

function wiggleSort($nums) {
    $n = count($nums);
    if ($n <= 1) {
        return $nums;
    }
    
    sort($nums);
    $result = array_fill(0, $n, 0);
    $low = 0;
    $high = $n - 1;
    $mid = 1;
    
    // 填充偶数索引位置（从0开始计数）
    for ($i = 0; $i < $n; $i += 2) {
        if ($i == $n - 1 || $nums[$low] < $nums[$high]) {
            $result[$i] = $nums[$low++];
        } else {
            $result[$i] = $nums[$high--];
        }
    }
    
    // 填充奇数索引位置（注意此时low和high可能已重合，但只需从剩余部分选择）
    for ($i = 1; $i < $n; $i += 2) {
        if ($low <= $high) {
            $result[$i] = $nums[$low++];
        } else {
            // 如果有剩余元素，但low和high已重合，直接填充剩余元素
            $result[$i] = $nums[$low];
        }
    }
    
    return $result;
}

Python 代码示例

def wiggleSort(nums):
    nums.sort()
    n = len(nums)
    result = [0] * n
    low, high = 0, n - 1
    for i in range(n):
        if i % 2 == 0:
            result[i] = nums[low]
            low += 1
        else:
            result[i] = nums[high]
            high -= 1
    return result

JavaScript 代码示例

function wiggleSort(nums) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const result = new Array(n).fill(0);
    let low = 0, high = n - 1;
    for (let i = 0; i < n; i++) {
        if (i % 2 === 0) {
            result[i] = nums[low++];
        } else {
            result[i] = nums[high--];
        }
    }
    return result;
}

码小课网站中有更多关于摆动排序问题的解析和相关算法内容的分享，欢迎大家前去学习交流。