324 摆动排序 II
给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]… 的顺序。
你可以假设所有输入数组都可以得到满足题目要求的结果。
示例 1：
输入：nums = [1,5,1,1,6,4]
输出：[1,6,1,5,1,4]
解释：[1,4,1,5,1,6] 同样是符合题目要求的结果，可以被判题程序接受。
示例 2：
输入：nums = [1,3,2,2,3,1]
输出：[2,3,1,3,1,2]
提示：
1 <= nums.length <= 5 * 104
0 <= nums[i] <= 5000
题目数据保证，对于给定的输入 nums ，总能产生满足题目要求的结果
进阶：你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗？
class Solution {public void wiggleSort(int[] nums) {// 保证 1/2length下标有序 完成荷兰国旗问题chessSort(nums);// 6 --- 3// 7 --- 3int mid = nums.length %2 ==1 ? (nums.length/2+1) : (nums.length/2);// int mid = nums.length/2;int smallIndex = mid-1;int midIndex = nums.length - 1;int index = 0;int [] result = new int[nums.length];while(smallIndex >=0 && midIndex >= mid){result[index++] = nums[smallIndex--];result[index++] = nums[midIndex--];}if(index == nums.length -1){if(smallIndex >= 0) {result[index++] = nums[smallIndex++];} else {result[index++] = nums[midIndex++];}}index =0;while (index<nums.length){nums[index] = result[index];index++;}}public void swap(int []nums, int begin, int end){int tmp = nums[begin];nums[begin] = nums[end];nums[end] = tmp;}public void chessSort(int[] nums){int mid = nums.length /2;int begin = 0;int end = nums.length -1;while (begin <= end) {int[] range = chessSortPartition( nums, begin, end);if(range[0] <= mid && range[1]>=mid){break;} else if (range[0] > mid){end = range[0] -1;}else if(range[1] < mid){begin = range[1] +1;}}}public int[] chessSortPartition(int[] nums, int begin, int end){if(begin > end){return new int[]{-1,-1};}if(begin == end){return new int[]{begin,begin};}int randNum = nums[(begin + new Random().nextInt(end-begin+1))];int beginIndex = begin -1;int endIndex = end +1;int index = begin;while(index<endIndex){if(nums[index] == randNum){index++;} else if(nums[index]<randNum){beginIndex++;swap(nums, index, beginIndex);index++;} else {endIndex --;swap(nums, index, endIndex);index = index;}}return new int[]{beginIndex+1,endIndex-1};}}
