1968. Array With Elements Not Equal to Average of Neighbors

Array With Elements Not Equal to Average of Neighbors

題目描述： 給定一個整數陣列 nums，重新排列使得對於每個 1 <= i <= n-2，nums[i] 不等於其左右鄰居的平均值。即 nums[i] != (nums[i-1] + nums[i+1]) / 2，等價於 2 * nums[i] != nums[i-1] + nums[i+1]。

解題思路： 最簡單的方法是構造一個「鋸齒形」（wiggle）排列：

1. 先將陣列排序。
2. 排序後，每兩個相鄰元素一組進行交換（交換 nums[1] 和 nums[2]、nums[3] 和 nums[4]...）。
3. 這樣形成小、大、小、大的交替模式，每個元素都是局部極值，自然不等於鄰居平均值。

為什麼有效？排序後所有元素是不同的（題目保證），交換相鄰對後每個非端點元素 nums[i] 必定嚴格大於或嚴格小於兩側鄰居，因此不可能等於它們的平均值。

時間複雜度：O(n log n) — 排序為主要開銷。

空間複雜度：O(1) — 若不計排序內部空間，僅使用常數額外空間（原地操作）。

分割交錯法 O(n log n)：排序後，前半放奇數位、後半放偶數位（或反之）。需要額外 O(n) 空間，但概念直觀。

隨機打亂法 O(n) 期望：反覆隨機打亂陣列直到滿足條件。理論上期望時間為 O(n)，但最壞情況不保證，實際不建議使用。

1. 是否存在 O(n) 的確定性演算法？（提示：考慮中位數分割）
2. 如果要求嚴格的 wiggle sort（nums[0] < nums[1] > nums[2] < ...），做法有何不同？
3. 如何證明排序後交換相鄰對一定滿足條件？