LeetCode 324. 摆动排序 II

2021-10-18 HGNULB 约 8 分钟

文章信息 8 个分类 5 个标签

分类

题目描述

✅ 324. 摆动排序 II

题意分析

要把给定数组重新排列，使它满足 nums[0] < nums[1] > nums[2] < nums[3] > ... 这样的交替关系，并且原地修改（函数没有返回值）。

最关键的约束信号是不等号全部为严格不等。相邻两个位置不允许相等，这一条把重复元素从「小麻烦」变成了整道题的核心难点：如果某个值出现得太多，无论怎么排都会有两份挤在相邻位置。

题目声明「输入保证有解」，这是一个可以放心使用的前提。它等价于说重复值的数量落在可安放的范围内，因此不需要写任何「无解则返回」的分支。

数组长度可达 $5 \times 10^4$，允许 $O(n \log n)$ 通过；同时题目给了进阶要求——$O(n)$ 时间、$O(1)$ 额外空间，提示存在基于快速选择的更优解。

边界包括：长度为 1（任何排列都合法）；长度为 2（只需保证前小后大）；以及大量重复值的输入，例如 [4, 5, 5, 6]，它是检验一切「交错填充」写法是否正确的最小反例。

解法：排序 + 交错填充

核心思路

先看一个几乎正确的朴素想法：把数组排好序，切成较小的一半和较大的一半，然后小的一半按升序填入偶数下标、大的一半按升序填入奇数下标。这个想法对不含重复值的输入完全正确，但它在 [4, 5, 5, 6] 上翻车——排序后小半是 [4, 5]、大半是 [5, 6]，升序交错得到 [4, 5, 5, 6]，下标 1 和下标 2 都是 5，严格大于不成立。

瓶颈找得到：升序填充会把两半的「交界处」放到相邻位置上。较小一半的最大值和较大一半的最小值在排序数组里本来就挨着，最容易相等，而升序填充恰好把它们安排成了邻居。

观察由此产生：既然交界处的两个值最危险，就让它们离得最远。把两半都改成从大到小取值——较小一半的最大值（也就是中位数）落到下标 0，较大一半的最小值落到最后一个奇数下标，两者被推到数组的两端。同理，两半内部的其余重复值也随之被拉开距离。

于是构造规则可以写成一个明确的映射：设升序数组为 sorted，令 left = (n - 1) / 2 指向较小一半的末尾、right = n - 1 指向较大一半的末尾，则结果满足 res[2i] = sorted[left - i]、res[2i + 1] = sorted[right - i]。这里 left 取 (n - 1) / 2 是为了让较小一半恰好含有 $\lceil n/2 \rceil$ 个元素，正好等于偶数下标的个数。

正确性可以这样理解：对每一对相邻位置，偶数位取的元素在排序数组中的下标总是比奇数位取的元素小 n - left - 1 个身位，因此只要这两个位置上的值相等，就意味着有超过合法上限那么多份相同的元素挤在中间；而题目保证有解，这种输入不会出现。换句话说，只要存在合法排列，这个构造就一定能给出一个。

解题步骤

复制原数组并对副本升序排序。必须用副本而不是原数组本身，因为后面要边读排序结果边往原数组写，两者共用同一块内存会互相覆盖。

令 left = (n - 1) / 2，right = n - 1。left 指向较小一半的最后一个元素（即中位数），right 指向整个数组的最大值。用 (n - 1) / 2 而不是 n / 2，是为了在 $n$ 为奇数时让较小一半多分到一个元素，与偶数下标的个数对齐。

从左到右填结果数组：下标为偶数时取 sorted[left] 并让 left 左移。偶数位是「谷」，应当取较小一半的值，且从大到小取才能把重复值推向后方。

下标为奇数时取 sorted[right] 并让 right 左移。奇数位是「峰」，取较大一半的值，同样从大到小取。两个指针各自单调左移，各扫各的半区，互不越界。

把结果数组整体拷回 nums，满足题目「原地修改」的接口要求。

以 [1, 5, 1, 1, 6, 4] 走一遍：$n = 6$，排序后 sorted = [1, 1, 1, 4, 5, 6]，初始 left = (6 - 1) / 2 = 2，right = 5。下标 0 是偶数，取 sorted[2] = 1，left 变 1；下标 1 是奇数，取 sorted[5] = 6，right 变 4；下标 2 取 sorted[1] = 1，left 变 0；下标 3 取 sorted[4] = 5，right 变 3；下标 4 取 sorted[0] = 1，left 变 -1；下标 5 取 sorted[3] = 4，right 变 2。得到 [1, 6, 1, 5, 1, 4]，逐对验证：$1 < 6$、$6 > 1$、$1 < 5$、$5 > 1$、$1 < 4$，全部严格成立。注意三个相同的 1 被分别放在下标 0、2、4，恰好互不相邻——这正是逆序取值带来的效果。

代码实现

class Solution {
    // 排序后把数组分成较小一半和较大一半，奇数位放较大值，偶数位放较小值。
    public void wiggleSort(int[] nums) {
        int n = nums.length;
        int[] sorted = nums.clone();
        Arrays.sort(sorted);

        int left = (n - 1) / 2;
        int right = n - 1;

        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                res[i] = sorted[left--];
            } else {
                res[i] = sorted[right--];
            }
        }

        System.arraycopy(res, 0, nums, 0, n);
    }
}

func wiggleSort(nums []int) {
    // 排序后把数组分成较小一半和较大一半，奇数位放较大值，偶数位放较小值。
    n := len(nums)
    sorted := make([]int, n)
    copy(sorted, nums)
    sort.Ints(sorted)

    left := (n - 1) / 2
    right := n - 1

    res := make([]int, n)
    for i := 0; i < n; i++ {
        if i%2 == 0 {
            res[i] = sorted[left]
            left--
        } else {
            res[i] = sorted[right]
            right--
        }
    }

    copy(nums, res)
}

复杂度分析

时间复杂度：$O(n \log n)$，代价由排序主导；复制、填充和拷回各是一次线性扫描，合计 $O(n)$，不改变量级。

空间复杂度：$O(n)$，需要一份排序副本和一份结果数组，两者都与输入等长。这也是本写法与进阶要求的差距所在——进阶解法用快速选择加三向切分，可以把空间压到 $O(1)$。

关键点总结

严格不等号是这道题的全部难度来源。一旦允许相等（对应 280 题），一次相邻扫描交换就能解决，根本用不到排序。判断题目属于哪一类，先看不等号严不严格。

处理重复值的通用思路是「最大化相同元素之间的距离」。本题通过两半都逆序取值，把最容易撞车的中位数附近的值推到数组两端，是这一思路最干净的实现。

划分点用 (n - 1) / 2 而不是 n / 2：偶数下标共有 $\lceil n/2 \rceil$ 个，较小一半必须恰好这么多元素才能填满，多一个少一个都会让两个指针的区间重叠或留空。

「排序结果」和「填充目标」必须是两块独立的内存。共用一块会边读边覆盖，这是所有重排类题目里最隐蔽的一类错误。

面试视角：面试官通常允许你先写这个 $O(n \log n)$ 版本，然后追问进阶。要能说出方向——用快速选择在 $O(n)$ 时间找到中位数并做三向切分，再用虚地址映射 $j \mapsto (1 + 2j) \bmod (n\ \ 1)$ 把三向切分直接作用在交错后的下标上，从而免掉额外数组。

面试视角：主动拿 [4, 5, 5, 6] 举例，说明「升序交错为什么会失败、逆序交错为什么就对了」，比直接把代码默写出来更能证明你理解了重复值这个真正的考点。

易错点总结

错误写法：两半都按升序取值交错填充。用例 [4, 5, 5, 6] → 排序后小半 [4, 5]、大半 [5, 6] 升序填入，得到 [4, 5, 5, 6]，下标 1 与下标 2 都是 5，严格大于不成立；正确结果形如 [5, 6, 4, 5]。

错误写法：先用一组无重复的数据验证升序交错，误以为写法正确。用例 [1, 1, 2, 2] → 升序交错恰好得到 [1, 2, 1, 2] 侥幸通过，换成 [4, 5, 5, 6] 立刻失败。含重复值的用例必须单独测。

错误写法：把 left 初始化为 n / 2。用例 [4, 5, 5, 6] → left = 2、right = 3，两个指针的取值区间重叠，sorted[2] = 5 被重复使用，得到 [5, 6, 5, 5]，下标 2 与 3 相等。

错误写法：不复制副本，直接对原数组排序后再往里填。用例任意输入 → 写入第一个位置时就破坏了尚未读取的排序结果，后续取到的全是被污染的值。

错误写法：奇偶下标的取值来源写反，偶数位取较大一半。用例 [1, 2] → 得到 [2, 1]，而题目要求 nums[0] < nums[1]，直接判错。

错误写法：把「先取值后自减」写成「先自减后取值」（sorted[--left]）。用例 [1, 2] → left 初始为 0，第一次就访问 sorted[-1]，下标越界抛异常。

错误写法：套用 280 题的相邻交换写法。用例 [4, 5, 5, 6] → 下标 2 处 nums[2] = 5 并不大于 nums[1] = 5，交换条件不触发，结果留下相邻相等；相邻交换只能保证非严格摆动。

错误写法：把结果留在局部数组里，忘记拷回 nums。用例任意输入 → 判题读取的是原数组，内容完全没变，直接判错；这类接口返回 void 的题目一定要检查最终写回。

相似题目

题目	难度	考察点
280. 摆动排序	中等	不等号非严格，允许相邻相等，一次扫描做相邻交换即可，无需排序
75. 颜色分类	中等	三向切分把等值元素聚成连续一段，目标与本题「把等值元素拆散」正好相反
215. 数组中的第K个最大元素	中等	快速选择本身，是本题 $O(n)$ 进阶解法里定位中位数的前置工具
376. 摆动序列	中等	不允许重排，求原序列中最长摆动子序列的长度，属于贪心或动态规划