这道题是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.最后就是三路快排,将小于、等于、大于的数组排序了,下面直接上代码。

博主的两版代码:

大牛的代码:

        OK,See You Next Chapter!

 

 

 

 

发表评论

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