題目連結：
題目意譯：
給定一整數陣列 nums，重新排列使其滿足 nums[0] < nums[1] > nums[2] < nums[3]……
你可以假設輸入陣列必定有著一組合法答案。
限制：
1 ≦ nums.length ≦ 5 × 10 ^ 4
0 ≦ nums[i] ≦ 5000
保證給定輸入 nums 必有一組答案。
進階： 你可以在 O(n) 時間且（或）原地（In-place）使用 O(1) 額外空間解出嗎？
範例測資：
範例 1：
輸入： nums = [1,5,1,1,6,4]
輸出： [1,6,1,5,1,4]
解釋： [1,4,1,5,1,6] 也可接受。
範例 2：
輸入： nums = [1,3,2,2,3,1]
輸出： [2,3,1,3,1,2]
解題思維：
首先我們可以看到題目所求等同於將陣列分成較小以及較大兩半（如果數字個數為奇數，則將最中間的數字丟到較小那一邊），然後將較大那一半反轉並一個數字一個數字安插到較小那一半兩兩數字之間。
因此我們可以直接排序，分成兩半，然後執行安插的動作即可。時間是 O(n log n)。
但如果我們需要達成進階的要求，則本題便變難不少：
先利用 O(n) 時間的作法找出中位數（作法可以參見這篇。不過如果使用的是 C++ 然後又懶得自己寫的話，可以呼叫 nth_element 來找到第 k 大元素，在此例即中位數）。
接著是較需要傷腦筋的部分：
我們做一次三方分割（Three-way Partitioning，參見維基的虛擬碼），把陣列的數字分成三種——大於中位數的、等於中位數的以及小於中位數的。而這邊我們要依序讓它們接在一起，形成大、中、小的關係（維基的是小、中、大，把虛擬碼的小於改大於、大於改小於即可），但是需要搭配一些重新索引（Reindex）之技巧。
例如現在我們有 nums = [9,6,8,7,5] 這五個數字，中位數是 7。此外如果我們取出索引值 0 、 1 、 2 、 3 、 4，並重新排列為 1 、 3 、 0 、 2 、 4（即奇數在前、偶數在後），然後把這些索引值對應的數字依序放到另一個陣列 X 裡。因此 X = [6,7,9,8,5]。
接著使用 X 去跑完分割後，並且在交換元素同時也交換 nums 中對應的元素，可以得到 X 變成
[8,9,7,5,6]
而此時的 nums 為
[7,8,5,9,6]
此即為所求排列。
因為這邊的三方分割會將 X 變成比中位數大的在前、跟中位數一樣的在中間，最後才接著比中位數小的數字。但是由於 X 實際上是 nums[1] 、 nums[3] 、 nums[0] 、 nums[2] 、 nums[4] 所組成。因此在 X 前半部放較大的那一半，對於原本的陣列 nums 即是在索引值 1 、 3 的位置放較大的那一半。而這即是題目需要的。
因此我們可以在 O(n) 得出所求。接著，來處理多出來的 O(n) 空間（即 X）。
可以看到 X 就是從 nums 中生出來的，而且我們分割時，動到 X 時同時也會動到相應位置的 nums。那為何不直接動 nums 就好呢？
觀察存取關係：
當我們存取 X[0] 時，實際上是存取 nums[1]；
當我們存取 X[1] 時，實際上是存取 nums[3]；
當我們存取 X[2] 時，實際上是存取 nums[0]；
當我們存取 X[3] 時，實際上是存取 nums[2]；
當我們存取 X[4] 時，實際上是存取 nums[4]。
因此當我們存取 X[i] 時，實際上是在存取 nums[(2i + 1) % n]，其中 n 代表陣列 nums 的長度，而「%」運算子代表著取餘之操作。不過這是 n 是奇數的情形，當 n 是偶數則為 nums[(2i + 1) % (n + 1)]。
而我們可以將奇偶的情況簡化成
nums[(2i + 1) % (n | 1)]
其中「|」為「或」（Or）之位元運算。
因此把程式碼原先存取 X[i] 之部分替換成 nums[(2i + 1) % (n | 1)] 即可將空間複雜度降至 O(1)。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
