? ? ?本文參考了https://discuss.leetcode.com/topic/32929/o-n-o-1-after-median-virtual-indexing/2，代碼參考了https://discuss.leetcode.com/topic/41464/step-by-step-explanation-of-index-mapping-in-java。
? ? ? 首先佛玄，我們使用快排的思想對原數(shù)組進行中位數(shù)的查找巢音，同時保證比中位數(shù)大的排在數(shù)組前面，然后是中位數(shù)拓型，最后是比數(shù)組小的數(shù)额嘿。在之前o(nlgn)解法中，我們排序好的數(shù)組重新排序劣挫，即從頭開始册养，奇數(shù)位置從前往后取原數(shù)組，偶數(shù)位置压固，從中位數(shù)往后取球拦，其實取法有很多種，都是為了防止數(shù)組的相等的數(shù)沖突。在這里刘莹，采取防止沖突方法是：即比中位數(shù)小的先排最后的偶數(shù)位置阎毅，比中位數(shù)大的先排前面的奇數(shù)位置，中位數(shù)補空点弯。（這樣來看扇调，中位數(shù)大于2個，無法滿足題意的排序）
? ?index ? ? ? ? ? ? ? ? ? ? 0 ? 1 ? ? ?2 ? ?3 ? 4 ? ? 5 ? ? 6 ? 7
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? L1 ? L2 ? L3 ?M ?M ? ?s1 ? s2 ? ?s3
virtual index ? ? ? ? ? ? 1 ? ? ?3 ? ? 5 ? ?7 ? 0 ? ? 2 ? ? 4 ? ? ?6
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?M ? ?L1 ? s1 ? L2 ?s2 ? L3 ? s3 ? ?M
可以看出virtual index = (1+2*index) % (len | 1)
這個只是暫時定義抢肛，其實最后得出結(jié)果并不是嚴格按照以上順序來的狼钮。
利用三次切分，將numbers[virtual index]和中位數(shù)進行比較捡絮，如果numbers[virtual index]大熬芜，就應(yīng)該放在前面，所以交換當前指針指向數(shù)字福稳；相等涎拉，指針繼續(xù)移動；否則的圆，應(yīng)該放在后面鼓拧，交換數(shù)字而且當前指針不動。
