BiruLyu
8/15/2017 - 11:17 PM

## 324. Wiggle Sort II(#).java

``````public class Solution {
public void wiggleSort(int[] nums) {
int[] sorted = nums.clone();
Arrays.sort(sorted);
int mid = (nums.length-1) / 2;
for(int i=0, j=mid, k=nums.length-1; i<nums.length; i+=2, j--, k--) {
nums[i] = sorted[j];
if (i+1<nums.length) nums[i+1] = sorted[k];
}
}
}``````
``````public class Solution {
private int findMedian(int[] nums) {
return findKthSmallest(nums, 0, nums.length - 1, (nums.length + 1) / 2);
}
private int findKthSmallest(int[] nums, int start, int end, int k) {
if (start == end) {
return nums[start];
}

int pivot = nums[start + (end - start) / 2];
int left = start;
int right = end;
while (left <= right) {
while (left <= right && nums[left] < pivot) {
left++;
}
while (left <= right && nums[right] > pivot) {
right--;
}
if (left <= right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
if (start + k - 1 <= right) {
return findKthSmallest(nums, start, right, k);
} else if (start + k - 1 >= left) {
return findKthSmallest(nums, left, end, k - (left - start));
} else {
return pivot; // return nums[start + k - 1];
}
}
private int getIdx(int idx, int n) {
return (1 + 2 * idx) % (n | 1);
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public void wiggleSort(int[] nums) {
int median = findMedian(nums);
int n = nums.length;
int left = 0, i = 0, right = n - 1;
while (i <= right) {
int cur = nums[getIdx(i, n)];
if ( cur > median) {
swap(nums, getIdx(i++, n), getIdx(left++, n));
} else if (cur < median) {
swap(nums, getIdx(i, n), getIdx(right--, n));
} else {
i++;
}
}
}
}``````