Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]….

Example: (1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6]. (2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].

Note: You may assume all input has valid answer.

Follow Up: Can you do it in O(n) time and/or in-place with O(1) extra space?

s思路: 1. 這道題一看，首先想到是用sort(),然后把后半部分和前半部分混和，例如:[1, 5, 1, 1, 6, 4],sort后得到[1,1,1,4,5,6],然后混合得到，[1,6,1,5,1,4].但這樣的復(fù)雜度是o(nlgn) 2. 題目要求o(n), 仔細想，這道題之要求wiggle sort,只要有這個wave的效果，并不需要嚴格的排序。那就用quick select先找到中點，然后把和中點值相等的通過three way partition給gather到靠近中點的位置，最后得到的就左邊值小的一個group,中間相等的一個group,右邊值稍微大的一個group.三個group得到后，一樣的進行混合，考慮到中間值可能重復(fù)的很多，在混合的時候，需要左右兩個part都從最大的值來混合，保證wiggle sort的 nums[0] < nums[1] > nums[2] < nums[3]….性質(zhì)，而不用擔(dān)心出現(xiàn)相等的情況！ 3. 總結(jié)一下過程：首先，quick select,把中間值放在(n-1)/2的坐標位置上，并且左邊是小于等于這個值，右邊是大于等于這個值，代碼中就是findMedian()這個函數(shù)，回憶一下這個函數(shù)的過程：初始時，left=0,right=n-1,k=(n-1)/2,然后選用left的位置作為pivot,然后找這個值在排好序的序列中的位置，這個找的過程可以寫成一個獨立的子函數(shù)叫partition,就是用two pointer來比較確定這個pivot應(yīng)該放的位置，例如：讓i=left+1,j=right,然后i和left比較，j和left比較，最后希望是o(n)找到left正確的位置即可，然后swap。這個過程就是quick sort的思想；第二步，由于第一步quick select只是把找到中值的位置，并且讓小于等于中值的數(shù)在左側(cè)，大于等于的在右側(cè)，這就有一個問題了，等于中值的可能分布在任意位置，必須把等于中值的放在一堆，才能保證nums[0] < nums[1] > nums[2] < nums[3]….，否則可能出現(xiàn)相等的情況，因此用threewaypartition用三個指針把數(shù)分堆，讓等于中值的數(shù)集合在一起。這里回憶一下整個過程，寫得很妙。 4. 接上文。因為要分三堆，也算是排序了，不過是很粗略的排序，用兩個指針分別指向左右邊界，然后用一個指針來遍歷所有的數(shù)，一共就三個指針，這是在做之前就要明確的問題的本質(zhì)和解題的規(guī)模。一共有兩種設(shè)置指針的方式，如下圖：圖的上半部分是把left和right指針的初始位置分別放在序列的兩端，這樣做，left往右移動，right往左移動，最后是融合成一部分；圖下半部分是另一種，把left和right初始位置放在了中值位置的左右，這么做，left則往左移動，right則往右移動，最后是分開的。所以在編寫代碼的時候，也發(fā)現(xiàn)第一種代碼簡單，但理解起來略困難，第二種則代碼復(fù)雜一些，但理解起來很容易，提供兩種思路，還是想說明：沒有那一種就一定比另一種好，只是站在不同的位置看待同一個問題。 5. 繼續(xù)描述。在找中值的時候，還可以利用c++的庫函數(shù)nth_element(start iterator, mid iterator, end iterator)比自己寫的都快！ 6. 這道題，最后要求做到o(1)的空間復(fù)雜度，就不容易了，因為上面的方法還是需要o(n)的空間。參考https://discuss.leetcode.com/topic/32929/o-n-o-1-after-median-virtual-indexing　膜拜牛人一下，看得似懂非懂了！以后再思考！