Leetcode_324_wigglySortII高质量C++代码

        这道题是Google的面试题，参照WigglySortI，本质就是一个坐标映射，只是中位数有等号，映射时候需要小心，博主第一版代码直接用Sort排序，代码击败65.8%，然后参照大牛代码，使用三路快排，速度已经提起来了。和大牛的代码不同的是，大牛采用高大上的宏函数做坐标映射，博主比较笨，理解那个映射公式花了些时间，索性就用了第一版代码的坐标映射，单独写了一个for循环。大牛代码103ms，博主代码102ms，所以坐标映射部分开销是差不多的，可见代码核心还是在三路快排（三指针）上。

总结一下：

        1.问题核心还是在于坐标映射，比中位数大的放到偶数坐标，比中位数小的放到奇数坐标下，等于中位数的时候就麻烦了

        2.等于中位数的情况要特别小心，中位数的数量大于n/2时无解，因为总会出现相等情况，

        中位数等于n/2时，需要将中位数优先填到最左或者最优，这时n必定为偶数，入 [4, 5, 5, 6]，填完之后是[4 5 5 6]还是[5 6 4 5]呢？就是说，要先填那个6，左大右小，从大向小填才能保证将可能临接的中位数隔开（否则小行的大数不在最右，大行的小数不在最左）。这就是坐标映射时候需要小心的了。

        3.最后就是三路快排，将小于、等于、大于的数组排序了，下面直接上代码。

博主的两版代码：

	void wiggleSort(vector<int>& nums) {
		const int n = nums.size();
		nth_element(nums.begin(), nums.begin() + n/2, nums.end());
		const int mid = nums[n/2];
		
		int i = 0, j = 0, k = n - 1;
		while (j <= k){
			if (nums[j] < mid){
				swap(nums[j++], nums[i++]);
			} else if (nums[j] > mid){
				swap(nums[j], nums[k--]);
			} else{
				j++;
			}
		}

		vector<int> wiggly(n);
		j = -1;
		for (i = n - 1; i >= 0; --i){
			j += 2;
			if (j >= n){
				j = 0;
			}
			wiggly[j] = nums[i];
		}
		swap(wiggly, nums);
	}

// 第一版代码简洁些：
	void wiggleSort_FirstEdition(vector<int>& nums) {
		vector<int> wiggly(nums.size());
		sort(nums.begin(), nums.end());

		int j = -1;
		for (int i = nums.size() - 1; i >= 0; --i){
			j += 2;
			if (j >= nums.size()){
				j = 0;
			}
			wiggly[j] = nums[i];
		}
		swap(nums, wiggly);
	}

大牛的代码：

void wiggleSort(vector<int>& nums) {
    int n = nums.size();
    
    // Find a median.
    auto midptr = nums.begin() + n / 2;
    nth_element(nums.begin(), midptr, nums.end());
    int mid = *midptr;
    
    // Index-rewiring.
    #define A(i) nums[(1+2*(i)) % (n|1)]

    // 3-way-partition-to-wiggly in O(n) time with O(1) space.
    int i = 0, j = 0, k = n - 1;
    while (j <= k) {
        if (A(j) > mid)
            swap(A(i++), A(j++));
        else if (A(j) < mid)
            swap(A(j), A(k--));
        else
            j++;
    }
}

        OK，See You Next Chapter!