LeetCode 280. 摆动排序

Categories:

题目描述
思路分析
1. 解法一：单次扫描交换（推荐）
相似题目

题目描述

✅ 280. 摆动排序

思路分析

解法一：单次扫描交换（推荐）

核心思路：

目标顺序为 nums[0] <= nums[1] >= nums[2] <= nums[3] ...。

从左到右扫描，当索引为奇数且 nums[i] < nums[i-1] 时交换；当索引为偶数且 nums[i] > nums[i-1] 时交换。

局部调整即可保证前缀满足摆动性质。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    public void wiggleSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            if ((i % 2 == 1 && nums[i] < nums[i - 1])
                    || (i % 2 == 0 && nums[i] > nums[i - 1])) {
                int tmp = nums[i];
                nums[i] = nums[i - 1];
                nums[i - 1] = tmp;
            }
        }
    }
}

func wiggleSort(nums []int) {
	for i := 1; i < len(nums); i++ {
		if (i%2 == 1 && nums[i] < nums[i-1]) || (i%2 == 0 && nums[i] > nums[i-1]) {
			nums[i], nums[i-1] = nums[i-1], nums[i]
		}
	}
}

相似题目

题目	难度	考察点
324. 摆动排序 II	中等	排序
376. 摆动序列	中等	贪心
75. 颜色分类	中等	双指针
905. 按奇偶排序数组	简单	双指针
283. 移动零	简单	双指针

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/49925607