Description

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?

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Solution

比較難的一道題衷笋，因?yàn)閿?shù)組中可能會(huì)有重復(fù)元素凑保，不考慮重復(fù)元素的話會(huì)造成nums[i] == nums[i + 1]這種情況笆怠，是不合要求的。

Quick select + Sort colors, time O(n), space O(1)

1. 使用O(n)時(shí)間復(fù)雜度的quickSelect算法矫废，從未經(jīng)排序的數(shù)組nums中選出中位數(shù)mid
2. 參照解法I的思路，將nums數(shù)組的下標(biāo)x通過(guò)函數(shù)idx()從[0, 1, 2, ... , n - 1, n] 映射到 [1, 3, 5, ... , 0, 2, 4, ...]，得到新下標(biāo)ix
3. 以中位數(shù)mid為界秫逝，將大于mid的元素排列在ix的較小部分，而將小于mid的元素排列在ix的較大部分询枚。
   詳見(jiàn)：https://leetcode.com/discuss/77133/o-n-o-1-after-median-virtual-indexing

class Solution {
   public void wiggleSort(int[] nums) {
        int median = findKthLargest(nums, (nums.length + 1) / 2);
        int n = nums.length;

        int left = 0, i = 0, right = n - 1;

        while (i <= right) {

            if (nums[newIndex(i,n)] > median) {
                swap(nums, newIndex(left++,n), newIndex(i++,n));
            }
            else if (nums[newIndex(i,n)] < median) {
                swap(nums, newIndex(right--,n), newIndex(i,n));
            }
            else {
                i++;
            }
        }


    }

    private int newIndex(int index, int n) {
        return (1 + 2*index) % (n | 1);
    }
    
    public int findKthLargest(int[] nums, int k) {
        return findKthLargest(nums, 0, nums.length - 1, k);
    }
    
    private int findKthLargest(int[] nums, int l, int r, int k) {
        int index = partition(nums, l, r);
        if (index == nums.length - k) {
            return nums[index];
        } else if (index < nums.length - k) {
            return findKthLargest(nums, index + 1, r, k);
        } else {
            return findKthLargest(nums, l, index - 1, k);
        }
    }
    
    private int partition(int[] nums, int l, int r) {
        int pivot = nums[r];
        int i = l;
        while (l < r) {
            if (nums[l] <= pivot) {
                swap(nums, l, i++);
            }
            ++l;
        }
        
        swap(nums, r, i);
        return i;
    }
    
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}