LeetCode 324：摆动排序 II | 三路分区的扩展

LeetCode 324摆动排序 II | 三路分区的扩展引言摆动排序 IIWiggle Sort II是 LeetCode 第 324 题难度为 Medium。题目要求将数组排序为摆动序列nums[0] nums[1] nums[2] nums[3] ...。与摆动排序 I 不同II 要求严格小于或大于不能相等。这道题需要先将数组排序然后使用特定的方式重新排列元素使得偶数位0, 2, 4...的元素小于相邻的奇数位元素。问题分析题目描述给定一个数组 nums重新排列数组元素使满足 nums[0] nums[1] nums[2] nums[3] ...。问题特点问题的关键在于如何处理重复元素。如果简单地将数组分成两半前半部分放在偶数位后半部分放在奇数位可能导致相邻元素相等的情况。正确的方法是先将数组排序然后将排序后的数组分成两部分较小的前 half 放在偶数位较大的后 half 放在奇数位。这样可以确保偶数位元素一定小于相邻的奇数位元素。解决方案排序后交叉放置def wiggleSort(nums): nums.sort() mid (len(nums) 1) // 2 - 1 first nums[:mid 1] second nums[mid 1:] result [] for i in range(len(second)): result.append(first[len(first) - 1 - i]) if i len(second) - 1 or len(second) len(first): result.append(second[len(second) - 1 - i]) if len(second) len(first): result.append(first[0]) for i in range(len(nums)): nums[i] result[i]算法详解将数组排序将数组分成两部分较小的一半first和较大的一半second逆序遍历 first 和 second交叉放置到结果数组如果两个部分长度不同较长部分的第一个元素放在最后复杂度分析时间复杂度时间复杂度为 O(n log n)因为需要排序。空间复杂度空间复杂度为 O(n)因为需要额外的数组存储结果。代码实现Python 实现def wiggleSort(nums): nums.sort() mid (len(nums) 1) // 2 - 1 first nums[:mid 1][::-1] second nums[mid 1:][::-1] result [] for i in range(max(len(first), len(second))): if i len(first): result.append(first[i]) if i len(second): result.append(second[i]) nums[:] result测试用例def test_wiggle_sort(): nums1 [1, 5, 1, 1, 6, 4] wiggleSort(nums1) assert nums1 [1, 6, 1, 5, 1, 4] or is_wiggle(nums1) nums2 [1, 3, 2, 2, 3, 1] wiggleSort(nums2) assert is_wiggle(nums2) print(所有测试用例通过) def is_wiggle(nums): for i in range(len(nums) - 1): if i % 2 0: if nums[i] nums[i 1]: return False else: if nums[i] nums[i 1]: return False return True总结摆动排序 II 展示了在排序后如何重新排列元素以满足摆动条件。关键是分成两部分后逆序交叉放置确保相邻元素不会相等。