[算法] [leetcode-324] 摆动排序 II
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 --- 3
int 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};
}
}