280. Wiggle Sort

280. Wiggle Sort

Question

Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]….

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

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Thinking:

• Method 1:O(NlgN)

class Solution {
    public void wiggleSort(int[] nums) {
        Arrays.sort(nums);
        int len = nums.length;
        int index = (len % 2 == 0) ? len / 2: len / 2 + 1;
        int[] arr = new int[index];
        int i = 0;
        for(; i < index; i++)
            arr[i] = nums[i];
        int[] sec = new int[len - index];
        for(; i < len; i++)
            sec[i - index] = nums[i];
        for(i = 0; i < index; i++){
            nums[2 * i] = arr[i];
            if(i < sec.length) nums[2 * i + 1] = sec[i];
        }
    }
}

• Method 2: O(N)
  • 对于奇数index，我们判断当前位和前一位的大小关系满足nums[i] >= nums[i - 1]
  • 对于偶数index，我们判断nums[i] <= nums[i - 1]

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