324 Wiggle Sort II

Note the corner case:

[1,1,1,2,2,3,3]
[1,1,2,2,3,3]
[1,1,1,2,2,2]
[1,1,1,1,2,2,2]
[1,1,1,2,2,2,2]
[4,5,5,6]

思路
这题好抓狂啊，看着很简单，但好多corner case；一定是我打开方式不对...所以用中文写来理理思路。

什么情况不能摇摆排序？

感觉有很多漏洞，再想一下

假设我们已经把数组排序好了：

$$a_1 \leq a_2 \leq ...... \leq a_l <mid_1 = mid_2 = ...... = mid_m < b_1 \leq b_2 ...... \leq b_g$$

先考虑一个偶数情形：$$l+m+g = 2N$$。
摇摆排序就是把后半段数组（$$n{(N+1) \sim 2N}$$）嵌套到前半段数组（$$n{1 \sim N}$$）中。具体有两种嵌套方式：
(1) $$n1, n{N+1}, n2, n{N+2}......nN, n{2N}$$
(2) $$nN, n{2N}, n{N-1}, n{2N-1}......n1, n{N+1}$$

有一种感觉，当中位数很多的时候不能排序。

偶数（2N）情况

当 m == N 时
example 1: [2, 2, 2, 3, 3, 3] :)
example 2: [1, 2, 2, 2, 3, 3]
  Method 1 :(
    first half:  1, 2, 2
    second half:  2, 3, 3
  Method 2 :)
    first reversed half:  2, 2, 1
    second reversed half:   3, 3, 2
example 3: [1, 1, 2, 2, 2, 3]
  Method 1 :(
    first half: 1, 1, 2
    second half: 2, 2, 3
  Method 2 :)
    first reversed half:  2, 1, 1
    second reversed half:   3, 2, 2

当 m == N+1 时
example 1: [1, 2, 2, 2, 2, 3] :(
example 2: [1, 1, 1, 1, 2, 2] :(

奇数（2N+1）情况：

当 m == N 时
example 1: [1, 1, 2, 2, 4] :)
  first reversed half: 2, 1, 1
  second reversed half:  4, 2

example 2: [1, 2, 2, 3, 3] :)
  first reversed half: 2, 2, 1
  second reversed half:  3, 3

当 m == N+1 时
example 1: [1, 2, 2, 2, 3] :(
example 2: [1, 1, 2, 2, 2] :(
example 3: [2, 2, 2, 3, 3] :)

所以对于长度为$$2N+1$$的数组，摇摆排序存在的条件是 $$m \leq N$$。

• 综上所述，一个数组能形成摇摆排序的条件是：中位数个数$$m$$满足：$$m \leq \frac{n}{2}$$, 其中$$n$$为数组长度。

算法。

1. 最简单的就是排序，然后用倒序的两段数组相互嵌套得到结果(Solution 1)；
2. 为了避免排序带来的$$O(NlogN)$$的时间复杂度，我们可以采用 3-way quick select的算法将数组分成三段，严格比中位数小的， 等于中位数的，以及严格比中位数大的(Solution 2)。
3. 上述两种解法都需要一个额外数组进行排序，如何利用$$O(1)$$空间复杂度进行嵌套的操作（还没想出来）？

Solution 1

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        vector<int> help = nums;
        sort(help.begin(), help.end());
        int n = nums.size();
        int j = n-1;
        for ( int i = 1; i <= n-1; i += 2 ) nums[i] = help[j--];
        for ( int i = 0; i <= n-1; i += 2 ) nums[i] = help[j--];
        return;
    }
};

Solution 2

class Solution {
public:
    void quickSort(vector<int>&nums, int start, int end, int mid) {
        int pivot = nums[start];
        int i = start+1, j = end, k = start+1;
        while ( k <= j ) {
            if ( nums[k] == pivot ) { k += 1; continue;}
            if ( nums[k] > pivot ) { swap(nums[k], nums[j--]); continue;}
            if ( nums[k] < pivot and k == i ) { k++; i++; continue;}
            if ( nums[k] < pivot and k != i ) { swap(nums[k], nums[i++]); continue;}
        }
        swap(nums[start], nums[i-1]);
        if ( mid >= i-1 and mid <= j ) return;
        if ( mid < i-1 ) quickSort(nums, start, i-2, mid);
        if ( mid > j ) quickSort(nums, j+1, end, mid);
        return;
    }
    void wiggleSort(vector<int>& nums) {
        vector<int> help = nums;
        int n = nums.size();
        quickSort(help, 0, n-1, (n-1)/2);
        int j = n-1;
        for ( int i = 1; i <= n-1; i += 2 ) nums[i] = help[j--];
        for ( int i = 0; i <= n-1; i += 2 ) nums[i] = help[j--];
        return;
    }
};

Notes
关于three-way quick sort: http://www.geeksforgeeks.org/3-way-quicksort/