摆动排序

题目表述

给你一个的整数数组 nums, 将该数组重新排序后使 nums[0] <= nums[1] >= nums[2] <= nums[3]...

输入数组总是有一个有效的答案。

示例 1

输入：nums = [3,5,2,1,6,4]

输出：[3,5,1,6,2,4]

解释：[1,6,2,5,3,4]也是有效的答案

示例二

输入：nums = [6,6,5,6,3,8]

输出：[6,6,5,6,3,8]

提示

$1<=nums.length<=5\ast {10}^4$

$0<=nums[i]<={10}^4$

输入的 nums 保证至少有一个答案。

进阶：你能在 O(n) 时间复杂度下解决这个问题吗？

解法

直觉告诉我们，可以直接交换元素实现

代码实现

from typing import List


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, 2):
            if nums[i - 1] > nums[i]:
                nums[i - 1], nums[i] = nums[i], nums[i - 1]
            if i + 1 < n and nums[i] < nums[i + 1]:
                nums[i], nums[i + 1] = nums[i + 1], nums[i]


if __name__ == "__main__":
    nums = [1, 3, 5, 6, 4, 2]
    Solution().wiggleSort(nums)
    print(nums)

package leetcode

// 直接交换元素
func wiggleSort(nums []int) {
	for i := range nums {
		if i%2 == 0 {
			continue
		}
		if nums[i] < nums[i-1] {
			nums[i], nums[i+1] = nums[i+1], nums[i]
		}
		if i+1 < len(nums) && nums[i] < nums[i+1] {
			nums[i], nums[i+1] = nums[i+1], nums[i]
		}
	}
}