难度: Medium
在一个整数数组中，“峰”是大于或等于相邻整数的元素，相应地，“谷”是小于或等于相邻整数的元素。例如，在数组{5, 8, 4, 2, 3, 4, 6}中，{8, 6}是峰， {5, 2}是谷。现在给定一个整数数组，将该数组按峰与谷的交替顺序排序。
示例:
输入: [5, 3, 1, 2, 3] 输出: [5, 1, 3, 2, 3]
提示：
nums.length <= 10000
Submission
运行时间: 27 ms
内存: 16.8 MB
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
for i in range(1,n):
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]
Explain
此题解的思路是遍历数组，确保偶数索引的元素是谷，奇数索引的元素是峰。具体来说，当遍历到偶数索引i时，如果当前元素nums[i]大于前一个元素nums[i-1]，则交换这两个元素；当遍历到奇数索引i时，如果当前元素nums[i]小于前一个元素nums[i-1]，则交换这两个元素。这样，通过一次遍历，就能够保证数组按照峰与谷的交替顺序排列。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
for i in range(1,n):
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]
Explore
在此算法中，从索引1开始遍历是因为我们需要比较当前元素（nums[i]）与其前一个元素（nums[i-1]）并根据条件可能进行交换。如果从索引0开始，那么nums[i-1]将是nums[-1]，即数组的最后一个元素，这在逻辑上不符合我们交替设置峰和谷的初衷，因为数组的开始没有前一个元素可以比较。因此，从索引1开始可以确保每个元素都有一个前一个元素可以进行比较和可能的交换。
在处理长度为奇数和偶数的数组时，此算法的基本逻辑是相同的，即都是尝试使偶数位置是谷，奇数位置是峰。不过，对于数组的最后一个元素，如果数组长度为奇数，则最后一个元素位于偶数位置（从0开始计数），这时应确保它是谷；如果数组长度为偶数，则最后一个元素位于奇数位置，应确保它是峰。因此，数组长度的奇偶性会影响最后一个元素的处理，但整体算法逻辑保持一致。
该算法通过条件判断`if i%2==0`和`else`确保理想情况下每个偶数索引位置的元素是谷，每个奇数索引位置的元素是峰。然而，这种方法可能不总是能够在所有情况下完美地交替峰和谷。特别是在存在重复元素或特定的顺序排列时，单次遍历可能无法完全确保每个偶数位置都小于相邻的奇数位置元素，反之亦然。在某些情况下，可能需要额外的调整或多次遍历以完全达到峰谷交替的效果。