324. Wiggle Sort II

https://leetcode.com/problems/wiggle-sort-ii/

已知偶數 index 的數字必須較小，奇數 index 的數字較大
若題目的要求是 nums[0] <= nums[1] => nums[2] <= nums[3]
則就只要使用 quick select 找出 nums 的中位數後，將中位數以左的數字放入偶數 index ；以右的數字放入奇數 index 即可
但題目要求的是 nums[0] < nums[1] > nums[2] < nums[3]
因此若與中位數大小相同的數字不只一個的話，就不能肆意的「將中位數以左的數字放入偶數 index 以右的數字放入奇數」
否則可能導致中位數被擺放在一起的情況發生

所以需要將 nums 分成三堆，分別是【< 中位數】、【= 中位數】和【> 中位數】
且由於需要符合 wiggle 的原因，擺放的方法需要調整
將數字分為三堆，可以使用 DNF 來進行
而過去在進行 DNF 時，【< 中位數】的值會從左邊開始擺起，【> 中位數】會從右邊擺起，【= 中位數】則會不斷夾在 left 和 right 之間

若將偶數 index 視為過去陣列中的"左邊"，奇數 index 視為"右邊"
也就是 len(nums)=10; A(0)=0, A(1)=2, A(2)=4, A(3)=6, A(4)=8, A(5)=1, A(6)=3, A(7)=5, A(8)=7, A(9)=9
如此若將數字由小至大放置的話，【< 中位數】的值會從 A(0) A(1) A(2)... 開始放起；【> 中位數】的值會從 A(9) A(8) A(7)... 開始放起
而最後【= 中位數】會落在 A(3) A(4) A(5) A(6)（隨意舉例），相當於 nums 偶數 index 的尾端以及奇數 index 的頭
由於中位數會從 nums 偶數 index 的尾端開始放起，因此會和奇數 index 的尾端成對，也就是【> 中位數】的那些值
這代表了中位數會優先和【> 中位數】湊一對，直到【> 中位數】不夠湊了，才會從奇數 index 頭端開始放起和【< 中位數】的值配對

這表示，除非【> 中位數】和【< 中位數】的個數都已耗盡，否則中位數之間不可能發生配對

以 SSSSMMMMLL 為例的話，使用 DNF 擺放完後的結果就會是 A(0)~A(3)=S, A(4)~A(7)=M, A(8)~A(9)=L
nums 實際上相當於 SMSMSMSLML 的排列，符合了題目所需

但是注意，以上狀況在 SSSMMMMMLL 時便會失敗
若按照以上規則，則 SSSMMMMMLL 會排出 SMSMSMMLML，但其實可以排成 MLMLSMSMSM
差別在於 SM + ML or ML + SM，SMML 是非法的組合，而 MLSM 是合法的
所以排序的順序要由大至小排列，而不能是由小至大

因此上方以小排至大的一些處理方式就需要調整

在非 worst case 的情況下
quick select 和 DNF 都是 $O(n)$ 時間複雜度和 $O(1)$ 空間複雜度

Takeaway

• quick select
• DNF