[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)

代码：

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

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;     } }