难度: Medium
给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。
你可以假设所有输入数组都可以得到满足题目要求的结果。
示例 1：
输入：nums = [1,5,1,1,6,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]
提示：
1 <= nums.length <= 5 * 1040 <= nums[i] <= 5000nums ，总能产生满足题目要求的结果
进阶：你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗？
运行时间: 33 ms
内存: 17.4 MB
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
将nums从小到大排序，第一个值从中间的值取，第二个值从最后一个值取，这样交替的逐步向前
"""
arr = sorted(nums)
n = len(nums)
mid = (n + 1) // 2
x,y = mid - 1,n - 1
i = 0
while i < n:
nums[i] = arr[x]
if (i + 1) < n:
nums[i+1] = arr[y]
i += 2
x -= 1
y -= 1
该题解的思路是先将原数组 nums 排序，然后从排序后数组的中间位置和末尾位置交替取元素放入原数组。通过这种方式，可以使得相邻元素尽量不相等，从而满足摆动排序的要求。
时间复杂度: O(nlogn)
空间复杂度: O(n)
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
将nums从小到大排序，第一个值从中间的值取，第二个值从最后一个值取，这样交替的逐步向前
"""
arr = sorted(nums) # 对原数组进行排序
n = len(nums)
mid = (n + 1) // 2 # 计算中间位置
x, y = mid - 1, n - 1 # 双指针分别指向中间位置和末尾位置
i = 0
while i < n:
nums[i] = arr[x] # 从中间位置取元素
if (i + 1) < n:
nums[i+1] = arr[y] # 从末尾位置取元素
i += 2 # 步长为2，交替取元素
x -= 1 # 中间位置指针向前移动
y -= 1 # 末尾位置指针向前移动
排序数组后从中间和末尾交替取值可以更好地确保摆动排序的效果，即相邻元素之间的差异尽可能大。通过这种方式，较小的一半和较大的一半交替出现，从而防止相邻元素大小相近，尤其是在有重复元素的情况下。这种方法相对直观且易于实现，可以有效地避免相邻的元素值相同或相近，从而满足摆动排序的需求。
对于奇数长度的数组，中间位置的元素是唯一的中点元素。在题解中的方法里，中间位置元素会被首先放入结果数组的首位。然后从这个中点元素的前一个元素和数组末尾的元素开始，向前交替填充剩余位置。这种处理方式确保了所有元素都被利用，并且尽量保持摆动特性。
是的，使用额外的数组存储排序后的结果确实违背了原地修改的要求。原地修改指的是不使用额外的存储空间或者只使用常数额外空间的情况下修改数组。要实现真正的原地修改，可以考虑使用特定的排序算法（如荷兰国旗问题的三向切分快速排序来分隔元素），然后利用数组索引技巧或原地交换元素来达到摆动排序的效果，但这样的方法通常比较复杂且难以正确实现。
在使用双指针方法时，通过将数组分为两部分（较小的一半和较大的一半），并从每部分的内部末端开始交替取元素，可以最大化元素之间的差异，从而满足摆动排序。即使在遇到重复元素的情况下，由于重复元素被分散在两个不同的部分中，它们不太可能相邻放置，从而减少了重复元素相邻的可能。如果排列后的数组中重复元素聚集在一起，从每个部分的末端开始取元素同样有助于减少相邻重复元素的情况。