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)`` 额外空间,但返回契约只要求完成合法重排。 自建示例 -------- 重复值需要分散到不同位置: .. code-block:: text 输入:nums = [1, 1, 2, 2, 3, 3] 修改后可以是:[2, 3, 1, 3, 1, 2] 解释:该结果满足 2<3>1<3>1<2,并且每个输入元素都恰好使用一次;其他满足严格摆动关系的排列也合法。 只有一个元素: .. code-block:: text 输入:nums = [5] 修改后:[5] 解释:不存在相邻元素需要比较,单元素数组天然满足要求。 把较小半部和较大半部交错放置 ------------------------------ 先排序得到整体顺序。摆动关系要求偶数位置是谷、奇数位置是峰,因此把较小的一半倒序填入偶数位置,把较大的一半倒序填入奇数位置。两半都倒序,是为了让同一半中相等的元素尽量隔开;如果从小到大填,重复值可能在相邻的谷位或峰位附近相遇。 设 ``small`` 指向较小半部的末端,``large`` 指向整个有序数组的末端。依次填写 ``0, 1, 2, ...``:偶数位置取 ``small`` 并向左移动,奇数位置取 ``large`` 并向左移动。较小半部的长度取 ``(n + 1) / 2``,这样奇数长度时中位数归入谷位。题目保证存在合法答案,在这个保证下两相邻位置分别来自适当的两半,严格摆动关系成立。 C++ 实现 -------- .. code-block:: cpp class Solution { public: void wiggleSort(std::vector& nums) { std::vector sorted = nums; std::sort(sorted.begin(), sorted.end()); int n = static_cast(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)``;它不追求进阶的线性时间,但代码直接体现了严格摆动所需的两半交错。