[LeetCode] Wiggle Sort II 擺動排序

Given an unsorted array <code>nums</code>, reorder it such that <code>nums[0] &lt; nums[1] &gt; nums[2] &lt; nums[3]...</code>.

Example:

(1) Given <code>nums = [1, 5, 1, 1, 6, 4]</code>, one possible answer is <code>[1, 4, 1, 5, 1, 6]</code>. 

(2) Given <code>nums = [1, 3, 2, 2, 3, 1]</code>, one possible answer is <code>[2, 3, 1, 3, 1, 2]</code>.

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?

Credits:

這道題給了我們一個無序數組，讓我們排序成擺動數組，滿足nums[0] &lt; nums[1] &gt; nums[2] &lt; nums[3]...，并給了我們例子。我們可以先給數組排序，然後在做調整。調整的方法是找到數組的中間的數，相當于把有序數組從中間分成兩部分，然後從前半段的末尾取一個，在從後半的末尾去一個，這樣保證了第一個數小于第二個數，然後從前半段取倒數第二個，從後半段取倒數第二個，這保證了第二個數大于第三個數，且第三個數小于第四個數，以此類推直至都取完，參見代碼如下：

解法一：

解法二：