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[i1]。如果不满足交换两者。如果 i 是奇数要求 nums[i] nums[i1]。如果不满足交换两者。复杂度分析时间复杂度时间复杂度为 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 更简单因为允许相邻元素相等。只需要一次遍历确保每个偶数位小于等于下一个元素每个奇数位大于等于下一个元素。
