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)``;它不追求进阶的线性时间,但代码直接体现了严格摆动所需的两半交错。