Wiggle Sort
Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....
For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].
public void wiggleSort(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
if ((i % 2 == 0) == (nums[i] > nums[i + 1])) {
swap(nums, i, i + 1);
}
}
}
II
Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....
Example:
(1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
(2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].
Not a good solution, time O(nlogn), space O(n)...
public void wiggleSort(int[] nums) {
if(nums.length < 2)
return;
Arrays.sort(nums);
int[] first = Arrays.copyOfRange(nums, 0, (nums.length + 1) / 2),
second = Arrays.copyOfRange(nums, (nums.length + 1) / 2, nums.length);
int i = first.length - 1, j = second.length - 1;
for(int k = 0; k < nums.length; k ++){
if((k & 1) == 0){
nums[k] = first[i --];
}else {
nums[k] = second[j --];
}
}
}