324. Wiggle Sort II (Medium)
https://leetcode.com/problems/wiggle-sort-ii/
Given an unsorted array nums
, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]...
.
Example 1:
Input:nums = [1, 5, 1, 1, 6, 4]
Output: One possible answer is[1, 4, 1, 5, 1, 6]
.
Example 2:
Input:nums = [1, 3, 2, 2, 3, 1]
Output: One possible answer is[2, 3, 1, 3, 1, 2]
.
Note:
You may assume all input has valid answer.
Follow Up:
Can you do it in O(n) time and/or in-place with O(1) extra space?
Solutions
class Solution {
// This problem is too complicated, do not try again
public void wiggleSort(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}
int len = nums.length;
// tmp is a temporary memory used to scan out the medium
int[] tmp = new int[len];
System.arraycopy(nums, 0, tmp, 0, nums.length);
// Sort out the medium by which the nums is divided into two relatively equal size
// parts and the elements in left section is smaller than that in right section.
int medium = partition(tmp, 0, len - 1, len / 2);
int[] ans = new int[len];
// This is critical
Arrays.fill(ans, medium);
// stands for even index slot
int evenPtr = 0;
// stands for odd index slot
int oddPtr = 1;
for (int i = 0; i < len; i++) {
// every even index swap in a smaller element in the left section.
if (nums[i] < medium) {
ans[evenPtr] = nums[i];
evenPtr += 2;
}
// every odd index swap in a larger element in the left section.
else if (nums[i] > medium) {
ans[oddPtr] = nums[i];
oddPtr += 2;
}
}
System.arraycopy(ans, 0, nums, 0, nums.length);
}
private int partition(int[] nums, int l, int r, int mid) {
int left = l;
int right = r;
int midVal = nums[left];
// Sort nums by descending order.
// Only left == right it will jumps out of the loop
while (left < right) {
// if left >= right is the cause to jump out the loop, left = right
while (left < right && nums[right] >= midVal) {
right--;
}
nums[left] = nums[right];
// if left >= right is the cause to jump out the loop, left = right
while (left < right && nums[left] <= midVal) {
left++;
}
nums[right] = nums[left];
}
if (left == mid) {
return midVal;
}
if (left < mid) {
return partition(nums, left + 1, r, mid);
}
// left > mid
return partition(nums, l, right - 1, mid);
}
}