这道题的思路和 sort color 类似，把所有的数分成三类：比 median 大，median， 比 median 小。这样的话我们先要找到 median
O(n) 时间 O(1) space 找到 median，可以联想用 quick sort 找第 k 大的元素 findKthLargest
算 index 的方法很好: (1 + 2 * index) % (n | 1)，其中 (n | 1) 的意义在于找到最接近 n 的大于等于 n 的值
public class Solution {
public void wiggleSort(int[] nums) {
int n = nums.length;
int median = findKthLargest(nums, (n + 1) / 2);
int left = 0, right = n - 1, i = 0;
while (i <= right) {
if (nums[getIndex(i, n)] > median) {
swap(nums, getIndex(i, n), getIndex(left, n));
left++;
i++;
} else if (nums[getIndex(i, n)] < median) {
swap(nums, getIndex(i, n), getIndex(right, n));
right--;
} else {
i++;
}
}
}
private int getIndex(int i, int n) {
return (1 + 2 * i) % (n | 1);
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
private int findKthLargest(int[] nums, int k) {
k = nums.length - k;
int left = 0, right = nums.length - 1;
while (left < right) {
int pos = partition(nums, left, right);
if (pos == k) {
break;
} else if (pos < k) {
left = pos + 1;
} else {
right = pos - 1;
}
}
return nums[k];
}
private int partition(int[] nums, int left, int right) {
int i = left, j = right + 1;
int pivot = nums[left];
while (true) {
while (i < right && nums[++i] < pivot);
while (j > left && nums[--j] >= pivot);
if (i >= j) break;
swap(nums, i, j);
}
swap(nums, left, j);
return j;
}
}