LeetCode 280：摆动排序 | 原地调整算法

LeetCode 280：摆动排序 | 原地调整算法

引言

摆动排序（Wiggle Sort）是 LeetCode 第 280 题，难度为 Medium。题目要求原地调整数组，使数组满足 nums[0] <= nums[1] >= nums[2] <= nums[3] ...。

与摆动排序 II 不同，I 允许相邻元素相等。这使得问题更简单：只需要在遍历过程中，确保每个偶数位（0, 2, 4...）的元素小于等于下一个元素。

问题分析

题目描述

给定数组 nums，重新排列数组使满足 nums[0] <= nums[1] >= nums[2] <= nums[3] ...

问题特点

由于允许相等，问题的约束更宽松。可以使用简单的遍历，在遇到不符合条件的元素时，交换相邻元素即可。

解决方案

贪心方法

def wiggleSort(nums): for i in range(len(nums) - 1): if (i % 2 == 0 and nums[i] > nums[i + 1]) or \ (i % 2 == 1 and nums[i] < nums[i + 1]): nums[i], nums[i + 1] = nums[i + 1], nums[i]

算法详解

遍历数组，对于每个位置 i：

• 如果 i 是偶数，要求 nums[i] <= nums[i+1]。如果不满足，交换两者。
• 如果 i 是奇数，要求 nums[i] >= nums[i+1]。如果不满足，交换两者。

复杂度分析

时间复杂度

时间复杂度为 O(n)，因为只需要一次遍历。

空间复杂度

空间复杂度为 O(1)，原地操作。

代码实现

Python 实现

def wiggleSort(nums): for i in range(len(nums) - 1): if i % 2 == 0: if nums[i] > nums[i + 1]: nums[i], nums[i + 1] = nums[i + 1], nums[i] else: if nums[i] < nums[i + 1]: nums[i], nums[i + 1] = nums[i + 1], nums[i]

测试用例

def test_wiggle_sort(): nums1 = [3, 5, 2, 1, 6, 4] wiggleSort(nums1) for i in range(len(nums1) - 1): if i % 2 == 0: assert nums1[i] <= nums1[i + 1] else: assert nums1[i] >= nums1[i + 1] print("所有测试用例通过！")

总结

摆动排序 I 比 II 更简单，因为允许相邻元素相等。只需要一次遍历，确保每个偶数位小于等于下一个元素，每个奇数位大于等于下一个元素。