Given an unsorted array nums, reorder it in-place such that
nums[0] <= nums[1] >= nums[2] <= nums[3]....
Notice
Please complete the problem in-place.
Example
Given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].
分析：
排序，从第三个开始，把它和前一个数互换。
public class Solution {
/**
* @param nums a list of integer
* @return void
*/
public void wiggleSort(int[] nums) {
if (nums == null || nums.length <= ) return;
Arrays.sort(nums);
for(int i = ; i < nums.length; i+=){
int tmp = nums[i-];
nums[i-] = nums[i];
nums[i] = tmp;
}
}
}
Given an unsorted array nums, reorder it such that
nums[0] < nums[1] > nums[2] < nums[3]....
Notice
You may assume all input has valid answer.
Example
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].
分析：
先sort, 然后用一个指针指向中间那个数，另一个指针指向最末尾那个数，然后依次把数放入到一个新数组里.
public class Solution {
/**
* @param nums a list of integer
* @return void
*/
public void wiggleSort(int[] nums) {
if (nums == null || nums.length <= ) return;
Arrays.sort(nums);
int[] temp = new int[nums.length];
// 两个指针 p, q. p 指向中间那个数，q指向最右边那个数。
// 不断交替把数放在temp数组里。
int mid = (temp.length + ) / - ;
int end = temp.length - ;
for (int i = ; i < temp.length; i++) {
if ((i & ) == ) {
temp[i] = nums[mid--];
} else {
temp[i] = nums[end--];
}
}
// put the numbers back to nums.
for (int i = ; i < temp.length; i++) {
nums[i] = temp[i];
}
}
}
还有一种方法，先把array中的median找出来，然后把小于median和大于median的值交叉放入新数组中。
该方法来自： http://buttercola.blogspot.com/2016/01/leetcode-wiggle-sort-ii.html
public class Solution {
public void wiggleSort(int[] nums) {
if (nums == null || nums.length <= ) {
return;
}
int n = nums.length;
// Step 1: Find median of the array, return the index of the median
int median = findMedian(nums, , n - , (n - ) / );
// Step 2: 3-way sort, put median in the middle,
// numbers less than median on the left,
// numbers greater than median on the right
int[] temp = new int[n];
int left = ;
int right = n - ;
for (int i = ; i < n; i++) {
if (nums[i] < nums[median]) {
temp[left] = nums[i];
left++;
} else if (nums[i] > nums[median]) {
temp[right] = nums[i];
right--;
}
}
// add median into the middle
for (int i = left; i <= right; i++) {
temp[i] = nums[median];
}
// Step 3: wiggle sort
left = (n - ) / ;
right = n - ;
for (int i = ; i < n; i++) {
if ((i & ) == ) {
nums[i] = temp[left];
left--;
} else {
nums[i] = temp[right];
right--;
}
}
}
private int findMedian(int[] nums, int lo, int hi, int k) {
if (lo >= hi) {
return lo;
}
int pivot = partition(nums, lo, hi);
if (pivot == k) {
return pivot;
}
if (pivot > k) {
return findMedian(nums, lo, pivot - , k);
} else {
return findMedian(nums, pivot + , hi, k);
}
}
private int partition(int[] nums, int lo, int hi) {
int pivot = nums[lo];
int i = lo + ;
int j = hi;
while (i <= j) {
while (i <= j && nums[i] < pivot) {
i++;
}
while (i <= j && nums[j] >= pivot) {
j--;
}
if (i <= j) {
swap(nums, i, j);
}
}
swap(nums, lo, j);
return j;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}