【中等】力扣算法题解析LeetCode280：摆动排序

关注底部名片达文汐，即可获得本题完整源码！

题目详情

给定一个无序的数组 nums，请将它原地重新排列成如下形式： nums[0] <= nums[1] >= nums[2] <= nums[3]….

示例: 输入：nums = [3,5,2,1,6,4] 输出：一个可能的答案是 [1,6,2,5,3,4] 或 [3,5,1,6,2,4]

提示:

• 原地修改数组，不使用额外空间。
• 数组总存在至少一个有效答案。

解题思路

核心条件分析：

• 奇数索引 i（如 1, 3, 5…）：需满足 nums[i] >= nums[i-1]（波峰）。
• 偶数索引 i（如 2, 4, 6…）：需满足 nums[i] <= nums[i-1]（波谷）。

贪心策略（O(n) 解法）：

时间复杂度 O(n)：仅需一次遍历。 空间复杂度 O(1)：原地交换，无额外空间。

代码实现（Java版）

class Solution {
public void wiggleSort(int[] nums) {
// 从索引1开始遍历（索引0无需处理）
for (int i = 1; i < nums.length; i++) {
boolean isOddIndex = (i % 2 == 1); // 判断当前是否为奇数索引
if (isOddIndex) {
// 奇数索引：若当前值 < 前一个值，交换
if (nums[i] < nums[i – 1]) {
swap(nums, i, i – 1);
}
} else {
// 偶数索引：若当前值 > 前一个值，交换
if (nums[i] > nums[i – 1]) {
swap(nums, i, i – 1);
}
}
}
}

// 交换数组中的两个元素
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}

代码说明

我的名片👇👇👇👇👇👇👇👇👇👇👇