[LeetCode]Wiggle Sort II

首先我们明确有哪些情况一定没有办法wiggle sort。假设数组长度为n:

1. 如果n为偶数，并且某一个数出现的次数大于n / 2次，我们一定无法wiggle sort，因为肯定会有相同的数挨在一起
2. 如果n为奇数
1. 出现最多的数的次数小于等于n / 2的话没有问题
2. 出现最多的数的次数大于n / 2的话，只有等于n / 2 + 1并且其他的数都是大于这个数才可以。我们把这个数放在index为偶数的地方，其他大于它的数放在奇数的地方

其他所有的情况，都可以用如下的策略解决，假设输入数组中位数为M：

• 所有大于M的数，从左向右，从大到小填满奇数位
• 所有小于M的数，从右向左，从小到大填满偶数位
• 剩下的位用M填满

可以看出这个方法没有办法解决上面提到的一定无解的方法，如果某个数出现次数大于n / 2，那么他一定是中位数，我们的方法一定会出现两个M挨着的情况。而其他情况，包括2.2，都可以解决。第一种方法我们用sort，然后分别填奇数偶数位即可，时间复杂度O(n * log n)，代码如下：

事实上，我们不需要把大于M和小于M的部分都排序，先用quick select找出中位数，然后用3 way quick sort把其分成三个区间即可。这样O(N)的时间即可完成，代码如下：