0324. Wiggle Sort II¶
题目信息¶
- 题号:
0324
- 难度:
Medium
- 主题:
数组重排、严格摆动、重复值、原地修改
- 原题:
- 重点:
相邻关系必须严格小于和大于交替、输入保证存在答案、任意合法排列均可
题目重述¶
给定整数数组 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);它不追求进阶的线性时间,但代码直接体现了严格摆动所需的两半交错。