LeetCode 324. 摆动排序 II
题目描述
题意分析
重新排列数组，使它严格满足
nums[0] < nums[1] > nums[2] < nums[3]...。偶数下标是谷，奇数下标是峰，所有相邻比较都不允许相等；每个原元素的出现次数必须保持，结果直接写回输入数组。题目保证存在合法排列，因此不需要处理无解输入。数组可能包含重复值，不能只做到小于等于、大于等于的非严格摆动。结果不要求唯一，基础解法可以使用额外空间，进阶再考虑线性时间和常数额外空间。
解法：排序 + 交错填充
核心思路
[!blue]
先排序，把较小的
ceil(n / 2)个元素作为谷，较大的floor(n / 2)个元素作为峰。谷比峰多一个或数量相同，正好对应偶数位置和奇数位置的数量。两部分都从大到小取：小半区从
(n - 1) / 2向左读，填入偶数位置；大半区从n - 1向左读，填入奇数位置。这样把小半区中较大的值放在靠左谷位，把大半区中较小的值留在靠右峰位，避免分界附近的相等值被紧挨着配对。每个峰对应的左谷，在排序数组中的下标相差
floor(n / 2)。若两者相等，排序后的中间至少有floor(n / 2) + 1个相同值。偶数长度下，这已经超过能用其他元素隔开的数量；奇数长度下，若某值恰好多于一半，有解就要求它占全部谷位、其他值都更大，因此也不会产生相等的峰谷配对。这里需要用到题目保证有解。所以每个峰严格大于它的左谷。谷值本身又按降序填充，下一个右谷不大于左谷，于是峰也严格大于右谷，两侧不等式同时成立。
读取排序副本，写入独立结果缓冲，最后复制回输入数组。读写分离可以避免尚未使用的排序元素被覆盖；这是一种清晰的基础方法，排序成本和线性辅助空间在后面的进阶中再优化。
解题步骤
- 复制输入并排序，保留独立的读取来源。
- 令小半区指针为
(n - 1) / 2，大半区指针为n - 1。- 按结果下标递增填充：偶数位置取小半区当前值，奇数位置取大半区当前值，各自向前移动指针。
- 将结果缓冲复制回
nums。
代码实现
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);
}
}
import "sort"
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 + 1))$，排序主导，交错填充和写回都是线性操作。
- 空间复杂度：$O(n)$，保存排序副本与结果缓冲。
关键点总结
[!green]
- 较小半区负责谷，较大半区负责峰，两边都倒序读取以拉开相等分界值。
- 峰大于左谷，右谷又不大于左谷，所以同一个峰的两侧都满足严格不等式。
- 写回输入与常数辅助空间是不同要求，基础方法使用线性缓冲。
解法二：中位数 + 虚拟下标三路划分
核心思路
[!blue]
不必完成全排序，只需找到按升序排列后下标
n / 2的中位数median。使用随机快速选择，每次原地分成小于、等于、大于基准的三段，只继续处理包含目标下标的一侧；目标落入相等段时就得到中位数，期望只需线性时间。接下来把大于中位数的元素放在峰位，小于中位数的元素放在谷位，相等元素填剩余位置。为让一次连续的三路划分直接作用于这些分散下标，定义虚拟位置
index(i) = (1 + 2 * i) % (n | 1)。n | 1是不小于n的奇数，这个映射会先依次访问全部奇数下标，再依次访问全部偶数下标，且每个位置恰好访问一次。在虚拟顺序上维护四段：
[0, left)大于中位数，[left, scan)等于中位数，[scan, right]尚未处理，(right, n)小于中位数。大值换到虚拟前端并同时推进left、scan；小值换到虚拟后端，只减少right，继续检查换回的未知值；相等时只推进scan。大于中位数的数量不会超过奇数峰位数量，因此它们都会进入峰位；小于中位数的数量也不会超过偶数谷位数量，因此从虚拟末端放置时都会进入谷位。剩下的相等值位于虚拟顺序中部，在实际数组上对应较右的剩余峰位与较左的剩余谷位。
若中位数出现次数不超过一半，这两段相等值之间有足够的其他元素隔开，不会形成相邻的相等峰谷。奇数长度下若中位数出现
(n + 1) / 2次，合法排列只能把它们全放在谷位，其余元素都更大；此时所有峰位先被大值填满，相等值也只会进入谷位。因而在有解前提下，最终两侧比较都是严格的。虚拟下标只是访问位置的计算方式，没有新建映射数组。选择中位数与最终划分都在原数组中交换元素，额外只保存常数个下标和基准值。
解题步骤
- 用随机三路快速选择找到升序下标
n / 2对应的中位数。- 初始化虚拟划分边界
left = scan = 0、right = n - 1。- 通过映射读取扫描位置：大值交换到虚拟前端，小值交换到虚拟后端，相等值保留在中间。
- 直到
scan > right，全部位置处理完，输入数组已经成为合法摆动排列。
代码实现
class Solution {
public void wiggleSort(int[] nums) {
int median = selectMedian(nums);
int n = nums.length;
int left = 0;
int scan = 0;
int right = n - 1;
while (scan <= right) {
int index = virtualIndex(scan, n);
if (nums[index] > median) {
swap(nums, virtualIndex(left, n), index);
left++;
scan++;
} else if (nums[index] < median) {
swap(nums, index, virtualIndex(right, n));
right--;
} else {
scan++;
}
}
}
private int selectMedian(int[] nums) {
int target = nums.length / 2;
int left = 0;
int right = nums.length - 1;
while (true) {
int pivot = nums[left + (int) (Math.random() * (right - left + 1))];
int less = left;
int scan = left;
int greater = right;
while (scan <= greater) {
if (nums[scan] < pivot) {
swap(nums, scan++, less++);
} else if (nums[scan] > pivot) {
swap(nums, scan, greater--);
} else {
scan++;
}
}
if (target < less) {
right = less - 1;
} else if (target > greater) {
left = greater + 1;
} else {
return pivot;
}
}
}
private int virtualIndex(int index, int n) {
return (1 + 2 * index) % (n | 1);
}
private void swap(int[] nums, int i, int j) {
int value = nums[i];
nums[i] = nums[j];
nums[j] = value;
}
}
import "math/rand"
func wiggleSort(nums []int) {
median := selectMedian(nums)
n := len(nums)
virtualIndex := func(i int) int {
return (1 + 2*i) % (n | 1)
}
left, scan, right := 0, 0, n-1
for scan <= right {
index := virtualIndex(scan)
if nums[index] > median {
first := virtualIndex(left)
nums[first], nums[index] = nums[index], nums[first]
left++
scan++
} else if nums[index] < median {
last := virtualIndex(right)
nums[index], nums[last] = nums[last], nums[index]
right--
} else {
scan++
}
}
}
func selectMedian(nums []int) int {
target := len(nums) / 2
left, right := 0, len(nums)-1
for {
pivot := nums[left+rand.Intn(right-left+1)]
less, scan, greater := left, left, right
for scan <= greater {
if nums[scan] < pivot {
nums[scan], nums[less] = nums[less], nums[scan]
scan++
less++
} else if nums[scan] > pivot {
nums[scan], nums[greater] = nums[greater], nums[scan]
greater--
} else {
scan++
}
}
if target < less {
right = less - 1
} else if target > greater {
left = greater + 1
} else {
return pivot
}
}
}
复杂度分析
- 时间复杂度：期望 $O(n)$，随机快速选择期望为线性，虚拟划分始终为线性；若基准持续产生极端划分，快速选择最坏仍为 $O(n^2)$。
- 空间复杂度：$O(1)$，快速选择使用循环，划分通过下标映射原地交换，没有递归栈或辅助数组。
关键点总结
[!green]
- 选择中位数只确定大小分组，不需要给每组内部排序。
- 虚拟顺序先奇后偶，让连续三路划分对应实际峰谷位置。
- 相等元素集中在虚拟中段，同时利用输入有解的保证避免相邻相等。
易错点总结
[!yellow]
- 两个半区升序交错，可能把相等分界值放成相邻位置，破坏严格不等式。
- 偶数长度时把小半区末端写成
n / 2，会错误多分配一个元素；应使用(n - 1) / 2。- 读取和覆盖同一份排序数据，可能提前改掉尚未使用的元素。
- 只生成新结果却不写回
nums，调用方看不到重排结果。- 虚拟下标直接对偶数
n取模，只会访问奇数位置，无法覆盖整个数组；模数应为n | 1。- 虚拟划分把小值换到末端后立刻推进扫描下标，会跳过从末端换回的未知元素。
- 进阶中的随机快速选择只有期望线性时间，不能把最坏复杂度也写成线性。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 280. 摆动排序 | 中等 | 原题只需非严格交替，本题相等元素不能相邻地破坏严格不等式，需要重新分布中位数两侧。 |
| 215. 数组中的第K个最大元素 | 中等 | 求中位数是三路划分的前置步骤，再配合虚拟下标放入峰谷位置。 |