https://leetcode.com/problems/wiggle-sort-ii/#/description
一开始想的方法是把数组复制一份，然后按最小、最大、最小...依次放数字，结果WA，错误代码：
class Solution {
public:
void wiggleSort(vector<int>& nums) {
int n = nums.size();
if (n == 0) return;
vector<int> nums_copy(nums.begin(), nums.end());
sort(nums_copy.begin(), nums_copy.end());
int k = 0, p = 0, q = n - 1;
bool sign = true; // smallest of the remaining numbers
while (k < n) {
if (sign) nums[k++] = nums_copy[p++];
else nums[k++] = nums_copy[q--];
sign = !sign;
}
}
};
比如下面这个例子：
[1,3,2,2,3,1]
按这个方法得到的输出是
[1,3,1,3,2,2]
，最后两个数不符合要求。在做的过程中，最小和最大数的差距逐渐缩小，导致最后无法达成严格的大小关系。可见这种方法最大的困难在于如何避免连续两个数相等（甚至可行解就很少）。
如果取完最小的，不取当前最大，取一个比较大的数？比如，这个“比较大的数”取排序完靠中间的。上面的例子，排序后是
1,1,2, | 2,3,3
，取右半边第一个数。但是还是有问题，比如
4,5,5,6
，按这个方法得到的是
4,5,5,6
，中间两个又相等了，当排序后中位数不止一个时，就会有这个问题。有效的克服办法是，小的从中间开始递减着取，大的从最大开始递减着取：
class Solution {
public:
void wiggleSort(vector<int>& nums) {
int n = nums.size();
if (n == 0) return;
vector<int> nums_copy(nums.begin(), nums.end());
sort(nums_copy.begin(), nums_copy.end());
int k = 0, p = (n-1)/2, q = n-1;
bool sign = true; // smallest of the remaining numbers
while (k < n) {
if (sign) nums[k++] = nums_copy[p--];
else nums[k++] = nums_copy[q--];
sign = !sign;
}
}
};
能不能优化？比如，完整的排序有没有必要？再看上面的操作，其实我们是想把整个数组划分成左右两部分，使得左边的比右边的小，然后左、右交替着取。这样就自然联想到了快速排序的partition操作，但是这里最好能够将划分做得均衡，因此可以求
kth largest element in an array
( https://leetcode.com/problems/kth-largest-element-in-an-array/ )。另外，除了均衡，仍然要克服中位数不止一个的情形，比如类似
4,5,5,5,5,6,6,6
的case，因此在做完划分最好将中位数调整一下位置：一种可行方法是把中位数全部挤到中间。
下面的参考代码，偷懒一下，划分的操作就用
std::nth_element
代替了。其他的部分都没变，只是把原来的排序换成了
nth_element()
+
refine()
，其中
refine()
就是调整中位数位置的操作。
时间复杂度：平均意义上是O(n)
空间复杂度：O(n)，O(1)的做法是在做完划分后交替着用交换构造结果
class Solution {
public:
void wiggleSort(vector<int>& nums) {
int n = nums.size();
if (n == 0) return;
vector<int> nums_copy(nums.begin(), nums.end());
int mid = (n - 1) / 2;
std::nth_element(nums_copy.begin(), nums_copy.begin() + mid, nums_copy.end());
refine(nums_copy, mid);
int k = 0, p = mid, q = n-1;
bool sign = true; // need a smaller number
while (k < n) {
if (sign) nums[k++] = nums_copy[p--];
else nums[k++] = nums_copy[q--];
sign = !sign;
}
}
private:
void refine(vector<int>& nums, int mid) {
int put_here = 0, mid_val = nums[mid];
// left part
for (int i = 0; i < mid; ++i) {
if (nums[i] != mid_val) nums[put_here++] = nums[i];
}
while (put_here < mid) nums[put_here++] = mid_val;
// right part
put_here = nums.size() - 1;
for (int i = nums.size()-1; i > mid; --i) {
if (nums[i] != mid_val) nums[put_here--] = nums[i];
}
while (put_here > mid) nums[put_here--] = mid_val;
}
};