题目地址：

https://www.lintcode.com/problem/wiggle-sort-ii/description

给定一个数组$A$，要求重排数组，使得$A[0]<A[1]>A[2]<A[3]>...$。题目保证答案存在。返回任意其中一个答案即可。

法1：排序。先对$A$由小到大排序，然后开两个指针$i$和$j$，$i$指向$(l_A-1)/2$，$j$指向$l_A-1$。接着开一个新数组，然后按次序，把$i$指向的数和$j$指向的数分别填到新数组里即可。

算法正确性证明： 设$A$已经排好序。接着用数学归纳法。当$l_A=1,2$的时候显然正确。当$l_A\ge 3$时，由于题目保证有解，所以$A[l_A-1]>A[(l_A-1)/2]$（否则的话$A[l_A-1]$这个数，其出现次数大于数组总长度的一半，那么无论怎么排，一定存在两个相邻的位置恰好是$A[l_A-1]$，与题目保证有解矛盾），然后先把这两个数填起来，得$(A[(l_A-1)/2],A[l_A-1],...)$，填完这两个数之后，剩余的数组也是排好序的，由数学归纳法，存在一种排法满足要求，接着只需要证明$A[l_A-1]>A[(l_A-1)/2-1]$，这个也是显然的，否则的话$A[l_A-1]$这个数也要出现超过一半。由数学归纳法，算法正确。

代码如下：

import java.util.Arrays; public class Solution { /* * @param nums: A list of integers * @return: nothing */ public void wiggleSort(int[] nums) { // write your code here Arrays.sort(nums); int len = nums.length; int[] tmp = new int[len]; int i = len - 1 >> 1, j = len - 1; int idx = 0; while (i >= 0 || j > len - 1 >> 1) { tmp[idx++] = nums[i--]; // 这里要判一下是否已经填满了，否则有可能会出界 if (idx < len) { tmp[idx++] = nums[j--]; } } // 再填回来 for (int k = 0; k < len; k++) { nums[k] = tmp[k]; } } }

时间复杂度$O(n\log n)$，空间$O(n)$。

法2：快速选择。试想，如果我们求出了$A$的中位数$m$（这里的中位数定义为在$A$排序的情况下，下标是$l_A/2$的数。如果数组长度为偶数，也可以取下标是$(l_A-1)/2$的数），我们就可以这样解决问题：开一个新数组$B$，长度与$A$一样，并把每个数都赋值为$m$，接着将原数组$A$里的不等于$m$的数穿插进去。具体穿插需要考虑数组的长度，如果$l_A$是偶数，那么需要的效果是$A[0]<A[1]>A[2]<...>A[l_A-2]<A[l_A-1]$，我们可以将比$m$大的数填到$A[1,3,5,...]$，将比$m$小的数填到$A[l_A-2,l_A-4,...]$，由于题目保证答案一定存在，所以$m$出现的次数一定不能超过$l_A/2$，所以填数的次数会大于等于$l_A/2$，从而会把值为$m$的数都隔开，会产生一个合法解；如果$l_A$是奇数，那么需要的效果是$A[0]<A[1]>A[2]<...>A[l_A-3]<A[l_A-2]>A[l_A-1]$，我们可以将比$m$大的数填到$A[1,3,5,...]$，将比$m$小的数填到$A[l_A-1,l_A-3,...]$，由上面类似的论证，也可以得到一个合法解。这里得到合法解的方式是，让值为$m$的数尽量分布在数组两端，以防它们相邻。而要求出中位数$m$可以用快速选择算法得到。之所以要挑中位数来做，是因为这样可以保证在填数的时候不会“填出界”，因为大于和小于$m$的数的个数不会超过$l_A/2$，这样就会把所有不等于$m$的数都完全填进$B$中，保证了最后所得的数组$B$所含数字和$A$是完全一样的。代码如下：

import java.util.Arrays; public class Solution { /* * @param nums: A list of integers * @return: nothing */ public void wiggleSort(int[] nums) { // write your code here int len = nums.length; int mid = partition(nums, 0, len - 1, len >> 1); int[] tmp = new int[len]; Arrays.fill(tmp, mid); int l = 1, r = (len % 2 == 0) ? len - 2 : len - 1; for (int i = 0; i < len; i++) { if (nums[i] > mid) { tmp[l] = nums[i]; l += 2; } else if (nums[i] < mid) { tmp[r] = nums[i]; r -= 2; } } for (int i = 0; i < len; i++) { nums[i] = tmp[i]; } } // 在nums[l, ..., r]中寻找排序后下标为rank的数 // （这里的意思是，想象一下将nums[l, ..., r]排好序并且下标从0计数，此时下标为rank的数） private int partition(int[] nums, int l, int r, int rank) { int left = l, right = r; swap(nums, l, l + (r - l >> 1)); int piv = nums[left]; // 做partition，把比piv大于等于的数放右边，小于等于的数放左边 while (left < right) { while (left < right && nums[right] >= piv) { right--; } nums[left] = nums[right]; while (left < right && nums[left] <= piv) { left++; } nums[right] = nums[left]; } // 把分割点的数填回去 nums[left] = piv; // 如果left - l < rank，说明要向右边找，并把左边的数去掉，所以下标要把排除掉的数的个数删掉； // 如果left - l > rank，说明要向左边找，下标不用变； // 如果left - l = rank，那么恰好找到了，返回之 if (left - l < rank) { return partition(nums, left + 1, r, rank - (left - l + 1)); } else if (left - l > rank) { return partition(nums, l, right - 1, rank); } else { return piv; } } private void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } }

时空复杂度$O(n)$（这里是平均时间复杂度）。