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

WiggleSortII

总结一下:

        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!

 

 

 

 

发表评论

邮箱地址不会被公开。 必填项已用*标注