0324. Wiggle Sort II

题目信息

题号:

0324

难度:

Medium

主题:

数组重排、严格摆动、重复值、原地修改

原题:

LeetCode 0324

重点:

相邻关系必须严格小于和大于交替、输入保证存在答案、任意合法排列均可

题目重述

给定整数数组 nums,在原数组上重新排列所有元素,使结果满足 nums[0] < nums[1] > nums[2] < nums[3] > ...。每个相邻比较都是严格不等式,相等元素不能放在需要形成峰谷关系的相邻位置上。

数组长度位于 [1, 5 * 10^4],每个元素位于 [0, 5000]。题目保证输入一定存在至少一种合法排列;存在多个答案时可以写回任意一个。进阶要求尝试达到 O(n) 时间或仅使用 O(1) 额外空间,但返回契约只要求完成合法重排。

自建示例

重复值需要分散到不同位置:

输入:nums = [1, 1, 2, 2, 3, 3]
修改后可以是:[2, 3, 1, 3, 1, 2]
解释:该结果满足 2<3>1<3>1<2,并且每个输入元素都恰好使用一次;其他满足严格摆动关系的排列也合法。

只有一个元素:

输入:nums = [5]
修改后:[5]
解释:不存在相邻元素需要比较,单元素数组天然满足要求。

把较小半部和较大半部交错放置

先排序得到整体顺序。摆动关系要求偶数位置是谷、奇数位置是峰,因此把较小的一半倒序填入偶数位置,把较大的一半倒序填入奇数位置。两半都倒序,是为了让同一半中相等的元素尽量隔开;如果从小到大填,重复值可能在相邻的谷位或峰位附近相遇。

设 small 指向较小半部的末端,large 指向整个有序数组的末端。依次填写 0, 1, 2, ...:偶数位置取 small 并向左移动,奇数位置取 large 并向左移动。较小半部的长度取 (n + 1) / 2,这样奇数长度时中位数归入谷位。题目保证存在合法答案,在这个保证下两相邻位置分别来自适当的两半,严格摆动关系成立。

C++ 实现

class Solution {
public:
    void wiggleSort(std::vector<int>& nums) {
        std::vector<int> sorted = nums;
        std::sort(sorted.begin(), sorted.end());

        int n = static_cast<int>(nums.size());
        int small = (n + 1) / 2 - 1;
        int large = n - 1;
        for (int i = 0; i < n; ++i) {
            if (i % 2 == 0) {
                nums[i] = sorted[small--];
            } else {
                nums[i] = sorted[large--];
            }
        }
    }
};

代码分析

排序只用于确定两个半部,写回时每个元素恰好从副本中取出一次;奇偶位置的索引安排也保留了所有重复元素。n == 1 时两个指针都指向唯一元素,不需要额外分支。时间复杂度为 O(n log n),额外空间为 O(n);它不追求进阶的线性时间,但代码直接体现了严格摆动所需的两半交错。