[LeetCode] Wiggle Sort II

参考：https://leetcode.com/discuss/77133/o-n-o-1-after-median-virtual-indexing

思路：
1）QucikSort 的方法找出中间值，时间O(n)，空间O(1)
2）参见参考链接，类似于给三种颜色排序，将高中低三种值各自规划成一组，由于其中涉及到数组索引的变换，使得实际得到的结果是高低穿插。例如：

数组值：高    高    高    中    中    低
原索引： 0      1      2      3      4      5
变换后： 3      0      4      1      5      2


依据变换索引给高中低值进行规划（顺序为高中低）：

变换后索引值： 0      1      2      3      4      5
数     组     值：高    高     高    中     中    低
原     索     引： 1      3      5      0      2      4

也就是

原     索     引： 0     1      2     3     4      5
数     组     值：中    高    中    高    低    中

这个方法的另一个好处是变换后中间值是相邻的，使得变换前中间值是岔开的，解决了[4, 5 , 5, 6]这种情况

时间O(n)，空间O(1)

代码：

public class Solution {
    public void wiggleSort(int[] nums) {
        if (nums == null || nums.length <= 1) return;
        int median = getMedian(nums);

        int higher = 0, lower = nums.length - 1, current = 0;
        while (current <= lower) {
            if (nums[reIndex(current, nums.length)] == median) {
                current++;
            }

            else if (nums[reIndex(current, nums.length)] < median) {
                swap(nums, reIndex(current, nums.length), reIndex(lower--, nums.length));
            }
            else swap(nums, reIndex(current++, nums.length), reIndex(higher++, nums.length));
        }
    }
   
    private int reIndex(int index, int n) {
        return (2*index + 1) % (n | 1);
    }

    private int getMedian(int[] nums) {
        int start = 0, end = nums.length - 1, target = nums.length / 2;
        while (true) {
            swap(nums, start, (start + end) / 2);
            int swapIndex = start, current = start + 1;
            while (current <= end) {
                if (nums[current] >= nums[start]) swap(nums, ++swapIndex, current);
                current++;
            }
            swap(nums, start, swapIndex);
            if (swapIndex - start == target) return nums[swapIndex];
            else if (swapIndex - start > target) end = swapIndex - 1;
            else {
                target -= (swapIndex - start + 1);
                start = swapIndex + 1;
            }
        }
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}