324. 摆动排序 II
题目描述
输入一个整数数组 nums。
重新排列它的元素，使相邻元素严格地一小一大交替出现：nums[0] < nums[1]，nums[1] > nums[2]，nums[2] < nums[3]，依此类推。直接在原数组上修改，函数无需返回值。
题目保证一定能排出这样的结果。符合要求的排法可能不止一种，给出任意一种都算正确。
示例 1
输入：nums = [1,5,1,1,6,4] 输出：[1,6,1,5,1,4]
解释：1 < 6 > 1 < 5 > 1 < 4。[1,4,1,5,1,6] 等排法同样正确。
示例 2
输入：nums = [1,3,2,2,3,1] 输出：[2,3,1,3,1,2]
解释：2 < 3 > 1 < 3 > 1 < 2。
数据范围
1 <= nums.length <= 5 * 10^40 <= nums[i] <= 5000- 输入保证存在符合要求的排列。
进阶：能否在 O(n) 时间内完成，或者只使用 O(1) 额外空间原地完成？
解题思路：排序 + 两半倒序穿插
先排序，把数组分成较小的前半段（长度 (n+1)//2）和较大的后半段。偶数位从前半段的末尾往前取，奇数位从后半段的末尾往前取。倒序取是关键：中位数附近的重复值会被分到两端去，不会相邻。
为什么正确
偶数位取得的值来自小半段，奇数位来自大半段；两个指针 j、k 同步从大到小移动，所以每个奇数位都大于两侧的偶数位。
复杂度分析
时间 O(n log n)，空间 O(n)。
易错点
如果正序交替取（小、大、小、大），中间的重复值可能恰好相邻，例如 [4,5,5,6] 会得到 [4,5,5,6] 而不满足条件。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
arr = sorted(nums)
n = len(nums)
mid = (n + 1) // 2
j = mid - 1
k = n - 1
for i in range(n):
if i % 2 == 0:
nums[i] = arr[j]
j -= 1
else:
nums[i] = arr[k]
k -= 1class Solution {
public void wiggleSort(int[] nums) {
int[] arr = nums.clone();
Arrays.sort(arr);
int n = nums.length;
int mid = (n + 1) / 2;
int j = mid - 1;
int k = n - 1;
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
nums[i] = arr[j];
j--;
} else {
nums[i] = arr[k];
k--;
}
}
}
}class Solution {
public:
void wiggleSort(vector<int>& nums) {
vector<int> arr(nums);
sort(arr.begin(), arr.end());
int n = nums.size();
int mid = (n + 1) / 2;
int j = mid - 1;
int k = n - 1;
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
nums[i] = arr[j];
j--;
} else {
nums[i] = arr[k];
k--;
}
}
}
};func wiggleSort(nums []int) {
arr := append([]int(nil), nums...)
sort.Ints(arr)
n := len(nums)
mid := (n + 1) / 2
j := mid - 1
k := n - 1
for i := 0; i < n; i++ {
if i%2 == 0 {
nums[i] = arr[j]
j--
} else {
nums[i] = arr[k]
k--
}
}
}var wiggleSort = function(nums) {
const arr = [...nums].sort((a, b) => a - b);
const n = nums.length;
const mid = Math.floor((n + 1) / 2);
let j = mid - 1;
let k = n - 1;
for (let i = 0; i < n; i++) {
if (i % 2 === 0) {
nums[i] = arr[j];
j--;
} else {
nums[i] = arr[k];
k--;
}
}
};function wiggleSort(nums: number[]): void {
const arr = [...nums].sort((a, b) => a - b);
const n = nums.length;
const mid = Math.floor((n + 1) / 2);
let j = mid - 1;
let k = n - 1;
for (let i = 0; i < n; i++) {
if (i % 2 === 0) {
nums[i] = arr[j];
j--;
} else {
nums[i] = arr[k];
k--;
}
}
}其他解法
排序把所有元素排好，简单可靠，O(n log n)；快速选择只找中位数并做三路划分，保留穿插所需的最少顺序信息，平均 O(n)。两者最后的倒序穿插步骤完全相同。
解法 2：快速选择中位数 + 三路划分 时间 平均 O(n)，最坏 O(n²)，空间 O(n)
穿插并不需要完全有序，只需知道中位数 m 并按“小于 m / 等于 m / 大于 m”分成三段。先用快速选择找到第 (n-1)/2 小的元素 m，再对副本做荷兰国旗三路划分，得到“小 | 等 | 大”的数组。最后和主解法一样：偶数位倒序取前半部分，奇数位倒序取后半部分。倒序保证两侧等于 m 的元素分别落在数组两端，不会相邻。
平均时间降到 O(n)，也说明了本题真正依赖的只是中位数划分。实现比直接排序复杂得多。这里取区间中间元素作枢轴，最坏情况 O(n²)，可改为随机枢轴。若要达到 O(1) 空间，还需要用“虚拟下标”原地划分。
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
n = len(nums)
arr = nums[:]
k = (n - 1) // 2
lo, hi = 0, n - 1
while True:
pivot = arr[(lo + hi) // 2]
lt, i, gt = lo, lo, hi
while i <= gt:
if arr[i] < pivot:
arr[lt], arr[i] = arr[i], arr[lt]
lt += 1
i += 1
elif arr[i] > pivot:
arr[gt], arr[i] = arr[i], arr[gt]
gt -= 1
else:
i += 1
if k < lt:
hi = lt - 1
elif k > gt:
lo = gt + 1
else:
m = pivot
break
lt, i, gt = 0, 0, n - 1
while i <= gt:
if arr[i] < m:
arr[lt], arr[i] = arr[i], arr[lt]
lt += 1
i += 1
elif arr[i] > m:
arr[gt], arr[i] = arr[i], arr[gt]
gt -= 1
else:
i += 1
j, r = (n + 1) // 2 - 1, n - 1
for i in range(n):
if i % 2 == 0:
nums[i] = arr[j]
j -= 1
else:
nums[i] = arr[r]
r -= 1class Solution {
// 在 arr[lo..hi] 上按 pivot 三路划分，返回等于 pivot 的区间 {lt, gt}
private int[] partition3(int[] arr, int lo, int hi, int pivot) {
int lt = lo, i = lo, gt = hi;
while (i <= gt) {
if (arr[i] < pivot) swap(arr, lt++, i++);
else if (arr[i] > pivot) swap(arr, gt--, i);
else i++;
}
return new int[]{lt, gt};
}
private void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
public void wiggleSort(int[] nums) {
int n = nums.length;
int[] arr = nums.clone();
int k = (n - 1) / 2, lo = 0, hi = n - 1, m;
while (true) {
int pivot = arr[(lo + hi) >>> 1];
int[] p = partition3(arr, lo, hi, pivot);
if (k < p[0]) hi = p[0] - 1;
else if (k > p[1]) lo = p[1] + 1;
else { m = pivot; break; }
}
partition3(arr, 0, n - 1, m);
int j = (n + 1) / 2 - 1, r = n - 1;
for (int i = 0; i < n; i++) nums[i] = (i % 2 == 0) ? arr[j--] : arr[r--];
}
}class Solution {
// 在 arr[lo..hi] 上按 pivot 三路划分，返回等于 pivot 的区间 [lt, gt]
pair<int, int> partition3(vector<int>& arr, int lo, int hi, int pivot) {
int lt = lo, i = lo, gt = hi;
while (i <= gt) {
if (arr[i] < pivot) swap(arr[lt++], arr[i++]);
else if (arr[i] > pivot) swap(arr[gt--], arr[i]);
else i++;
}
return {lt, gt};
}
public:
void wiggleSort(vector<int>& nums) {
int n = nums.size();
vector<int> arr = nums;
int k = (n - 1) / 2, lo = 0, hi = n - 1, m;
while (true) {
int pivot = arr[(lo + hi) / 2];
auto [lt, gt] = partition3(arr, lo, hi, pivot);
if (k < lt) hi = lt - 1;
else if (k > gt) lo = gt + 1;
else { m = pivot; break; }
}
partition3(arr, 0, n - 1, m);
int j = (n + 1) / 2 - 1, r = n - 1;
for (int i = 0; i < n; i++) nums[i] = (i % 2 == 0) ? arr[j--] : arr[r--];
}
};func wiggleSort(nums []int) {
n := len(nums)
arr := append([]int(nil), nums...)
// 在 arr[lo..hi] 上按 pivot 三路划分，返回等于 pivot 的区间 [lt, gt]
partition3 := func(lo, hi, pivot int) (int, int) {
lt, i, gt := lo, lo, hi
for i <= gt {
if arr[i] < pivot {
arr[lt], arr[i] = arr[i], arr[lt]
lt++
i++
} else if arr[i] > pivot {
arr[gt], arr[i] = arr[i], arr[gt]
gt--
} else {
i++
}
}
return lt, gt
}
k, lo, hi, m := (n-1)/2, 0, n-1, 0
for {
pivot := arr[(lo+hi)/2]
lt, gt := partition3(lo, hi, pivot)
if k < lt {
hi = lt - 1
} else if k > gt {
lo = gt + 1
} else {
m = pivot
break
}
}
partition3(0, n-1, m)
j, r := (n+1)/2-1, n-1
for i := 0; i < n; i++ {
if i%2 == 0 {
nums[i] = arr[j]
j--
} else {
nums[i] = arr[r]
r--
}
}
}var wiggleSort = function(nums) {
const n = nums.length;
const arr = nums.slice();
// 在 arr[lo..hi] 上按 pivot 三路划分，返回等于 pivot 的区间 [lt, gt]
const partition3 = (lo, hi, pivot) => {
let lt = lo, i = lo, gt = hi;
while (i <= gt) {
if (arr[i] < pivot) {
[arr[lt], arr[i]] = [arr[i], arr[lt]];
lt++;
i++;
} else if (arr[i] > pivot) {
[arr[gt], arr[i]] = [arr[i], arr[gt]];
gt--;
} else {
i++;
}
}
return [lt, gt];
};
const k = (n - 1) >> 1;
let lo = 0, hi = n - 1, m;
while (true) {
const pivot = arr[(lo + hi) >> 1];
const [lt, gt] = partition3(lo, hi, pivot);
if (k < lt) hi = lt - 1;
else if (k > gt) lo = gt + 1;
else { m = pivot; break; }
}
partition3(0, n - 1, m);
let j = ((n + 1) >> 1) - 1, r = n - 1;
for (let i = 0; i < n; i++) nums[i] = i % 2 === 0 ? arr[j--] : arr[r--];
};function wiggleSort(nums: number[]): void {
const n = nums.length;
const arr = nums.slice();
// 在 arr[lo..hi] 上按 pivot 三路划分，返回等于 pivot 的区间 [lt, gt]
const partition3 = (lo: number, hi: number, pivot: number): [number, number] => {
let lt = lo, i = lo, gt = hi;
while (i <= gt) {
if (arr[i] < pivot) {
[arr[lt], arr[i]] = [arr[i], arr[lt]];
lt++;
i++;
} else if (arr[i] > pivot) {
[arr[gt], arr[i]] = [arr[i], arr[gt]];
gt--;
} else {
i++;
}
}
return [lt, gt];
};
const k = (n - 1) >> 1;
let lo = 0, hi = n - 1, m = 0;
while (true) {
const pivot = arr[(lo + hi) >> 1];
const [lt, gt] = partition3(lo, hi, pivot);
if (k < lt) hi = lt - 1;
else if (k > gt) lo = gt + 1;
else { m = pivot; break; }
}
partition3(0, n - 1, m);
let j = ((n + 1) >> 1) - 1, r = n - 1;
for (let i = 0; i < n; i++) nums[i] = i % 2 === 0 ? arr[j--] : arr[r--];
}