324. Wiggle Sort II

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....

Example: (1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].

(2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].

Note: You may assume all input has valid answer.

Follow Up: Can you do it in O(n) time and/or in-place with O(1) extra space?

Solution

first sort the array, then cut the array 2 parts, each round , pick a number from the end of each parts.

public class Solution {
    public void wiggleSort(int[] nums) {
        if(nums == null ) return ;

        int[] tmp = Arrays.copyOf(nums, nums.length);
        Arrays.sort(tmp);
        int i=0;
        int j=tmp.length;
        int k = (tmp.length+1)/2;

        for(i=0; i< nums.length; i++){
            nums[i] = (i & 1) == 0 ?  tmp[--k] : tmp[--j];
        }  

    }
}

How to do the follow up ??