280. Wiggle Sort

Leetcode Array Sort

Given an unsorted array nums, reorder it in-place such that

nums[0] <= nums[1] >= nums[2] <= nums[3]....

Example:

Given nums = [3, 5, 2, 1, 6, 4], 
one possible answer is [1, 6, 2, 5, 3, 4].

分析

根据题目要求的nums[0] <= nums[1] >= nums[2] <= nums[3]....，我们可以总结出如下规律：

• 当$i$为奇数时，nums$[i]$ >= nums$[i - 1]$
• 当$i$为偶数时，nums$[i]$ <= nums$[i - 1]$

那么我们只要对每个数字，根据其位置奇偶性，跟其对应的条件比较，如果不符合就和前面的数交换位置即可。

public void wiggleSort(int[] nums) {
    if (nums == null || nums.length <= 1) return;
    for (int i = 1; i < nums.length; i++) {
        boolean isOdd = i % 2 == 1;
        if (isOdd && nums[i] < nums[i - 1]) swap(nums, i, i - 1);
        else if (!isOdd && nums[i] > nums[i - 1]) swap(nums, i, i - 1);
    }
}

private void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}