324. 摆动排序 II

分析

该题属于非常规题目，在以前属于Hard难度（近期改成了Medium），属于有些大公司喜欢考察拉开差距的题目。该题有两种解法，一种时间复杂度较高，但容易理解，另一种时间复杂度较低，但难一些理解。

正解做法

首先讲解答案的做法，再去证明它的有效性。假设有数组，经过$O(nlogn)$时间排序后，得到[1,1,1,5,6]，我们将其分为等长的两部分，[1,1,1]和[5,6]。然后，倒序从两部分取数，得到[1,6,1,5,1]。当数组数量为偶数时，这个做法不变。
什么时候问题有解？

• 当数组里元素最多重复的次数小于等于$\lfloor n/2\rfloor$时，该问题有解，用上文做法一定能找到解。
• 然后有个特殊情况，当数组数量为奇数，最多重复次数为$\lceil n/2\rceil$，且重复元素是最小值时，比如[1,1,1,5,6]，问题也有解。
• 否则问题无解。
  • 条件2的其它情况满足，但重复的元素并非最小值时，比如数组是[1,1,5,5,5]时，该数组无解。
  • 如果重复次数过多，比如数组是[1,5,5,5]，该数组也无解。
  • 留意到，如果数组数量为偶数，且重复次数为$\lceil n/2\rceil$，此时满足条件1，仍然是有解的。

下文需要证明：

1. 为什么最多元素重复次数≤$\lfloor n/2\rfloor$时，用该做法一定有解？
2. 为什么最多元素重复次数=$\lceil n/2\rceil$，数组数为奇数个，且重复元素是最小值时，问题仍然有解？
3. 为什么最多元素重复次数≥$\lceil n/2\rceil$，却不满足条件2时，数组无解？

证明1

分为数组数量为偶数和奇数的情况讨论。
假如数组数量为偶数，比如[1,1,1,5,6,7]，分为[1,1,1]和[5,6,7]两部分。假如取x[i]为arr[a]，且x[i+1]>x[i]，则x[i+1]为arr[a+n/2]。

• 后者在前者的右侧，且数组有序，所以后者一定大于或等于前者。
• 假如两个元素相等，结合数组有序的特征，它们中间的数也一定相等，那么重复次数为n/2+1次，与题设相悖。所以后者一定不等于前者

综上，后者一定大于前者。所以这种取法能满足需求。

而取x[i+2]时，为了维持x[i+2] 以此类推，我们能证明x[0]x[2]，…所以该做法一定合法。

假如数组数量为奇数，分为两组后同理也可证该做法合法，因为较小一组的元素数为$\lfloor n/2\rfloor$，所以任取x[i]与x[i+1]，在原数组中的跨度也至少是 ⌊ n / 2 ⌋ \left \lfloor n/2 \right \rfloor