280. Wiggle Sort

最后更新

二刷

这个题做得真蠢。上来想的复杂了，想的是quick sort之类的，然后一个一个交换。

实际上直接交换就行。。没啥特别的。

回头看一刷也是同样的思考过程= =宿命论啊。。

Time: O(n)
Space: O(1)

public class Solution {
    public void wiggleSort(int[] nums) {
        if (nums.length <= 1) return;
        
        for (int i = 1; i < nums.length; i++) {
            if (i % 2 == 0 && nums[i] > nums[i-1]) {
                swap(i, i-1, nums);
            } else if (i % 2 != 0 && nums[i] < nums[i-1]) {
                swap(i, i-1, nums);
            }
        }
        return;
    }
    
    public void swap(int l, int r, int[] nums) {
        int temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }
}

一刷

这个题一开始蠢了，先SORT了一下，然后IN-PLACE做了半天。。

发现直接greedy就可以。。。。。。

public class Solution {
    public void wiggleSort(int[] nums) 
    {
        if(nums.length<=1) return;
       
        for(int i = 0; i < nums.length-1;i++)
        {
            if(i%2==0)
            {
                if(nums[i] > nums[i+1])
                {
                    swap(nums,i,i+1);
                }
            }
            else
            {
                if(nums[i] < nums[i+1])
                {
                    swap(nums,i,i+1);
                }
            }
        }
    }
    
    public void swap(int[] nums, int i, int j)
    {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}