Question

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

Example 1:

Input: nums = [1, 5, 1, 1, 6, 4]
Output: One possible answer is [1, 4, 1, 5, 1, 6].

Example 2:

Input: nums = [1, 3, 2, 2, 3, 1]
Output: One possible answer is [2, 3, 1, 3, 1, 2].

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[index - i - 1];
            if(2 * i + 1 < len)
                nums[2 * i + 1] = sec[sec.length - i - 1];
        }
    }
}