Wiggle Sort II
Given an unsorted array nums
, reorder it such that
nums[0] < nums[1] > nums[2] < nums[3]....
注意事项
You may assume all input has valid answer.
样例
Given nums = [1, 5, 1, 1, 6, 4]
, one possible answer is [1, 4, 1, 5, 1, 6]
.
Given nums = [1, 3, 2, 2, 3, 1]
, one possible answer is [2, 3, 1, 3, 1, 2]
.
挑战
Can you do it in O(n) time and/or in-place with O(1) extra space?
解题
先进行排序,然后从中位数mid开始
mid放在第一个位置 len-1放在第二个位置
mid-1放在第三个位置,len-2放在第四个位置
一直进行下去。。。
这样的思想就是让大数和小数交叉排列
public class Solution {
/**
* @param nums a list of integer
* @return void
*/
public void wiggleSort(int[] nums) {
// Write your code here
if(nums == null || nums.length == 0)
return;
Arrays.sort(nums);// 排序
int[] temp = new int[nums.length];
int mid = nums.length%2==0?nums.length/2-1:nums.length/2;// 中间下标
int index = 0;
for(int i=0;i<=mid;i++){
temp[index] = nums[mid-i];
if(index+1<nums.length)
temp[index+1] = nums[nums.length-i-1];
index = index+2;
}
for(int i=0;i<nums.length;i++){
nums[i] = temp[i];
}
}
}