说一说程序员“举一反三”的能力

jopen 4年前

说一说程序员“举一反三”的能力

题图:“私想者”

        获得思想的能力,我们称之为智力。解决一个问题,如果你能做到举一反三,那么你就真正获得了解决这一类问题的思想了。

        好吧,我们一起来体会一下自己“举一反三”的能力究竟怎么样。

        一、从快速排序说起

        快速排序可以说是应用最广的一种排序算法。其思想是基于分治模式,将问题不断缩小,对小的问题进行排序,合并,后最终完成排序。

        其中,快速排序最为核心的一个步骤是划分(partition)待排序数组:从数组中选择一个元素(主元),然后以这个主元为基准,将数组划分成两部分,使得前边部分元素都小于主元,后边部分元素都大于主元。(这里假设为从小到大排序),更详细的快速排序介绍见此文:快速排序

        如下图所示为一个划分数组的实例,这里选取数组的最后一个元素作为主元。

说一说程序员“举一反三”的能力

        其伪代码如下:

//核心函数,对数组A[p,r]进行就地重排,将小于A[r]的数移到数组前半部分,  将大于A[r]的数移到数组后半部分。 PARTITION (A,p,r)      pivot <—— A[r]      i <—— p-1 for j <—— p to r-1 do if A[j] < pivot              i <—— i+1             exchange A[i]<——>A[j]      exchange A[i+1]<——>A[r]return i+1

         二、如果你理解了快速排序算法思想

        假设你知道并理解了快速排序算法,我们接下来解决如下一个问题。

        问题描述:

        输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。要求时间复杂度为O(n)。

        分析与解答:

        最容易想到的办法是从头扫描这个数组,每碰到一个偶数,拿出这个数字,并把位于这个数字后面的所有数字往前挪动一位。挪完之后在数组的末尾有一 个空位,然后把该偶数放入这个空位。由于每碰到一个偶数,需要移动O(n)个数字,所以这种方法总的时间复杂度是O(n^2),不符合题目要求。

        事实上,若把奇数看做是小的数,偶数看做是大的数,那么按照题目所要求的奇数放在前面偶数放在后面,就相当于小数放在前面大数放在后面,联想到 快速排序中的 partition 过程,不就是通过一个主元把整个数组分成大小两个部分么,小于主元的小数放在前面,大于主元的大数放在后面。

        而 partition 过程有以下两种实现:

  1. 一头一尾两个指针往中间扫描,如果头指针遇到的数比主元大且尾指针遇到的数比主元小,则交换头尾指针所分别指向的数字;
  2. 一前一后两个指针同时从左往右扫,如果前指针遇到的数比主元小,则后指针右移一位,然后交换各自所指向的数字。

        类似这个 partition 过程,奇偶排序问题也可以分别借鉴 partition 的两种实现解决。

        为何?比如 partition 的实现一中,如果最终是为了让整个序列元素从小到大排序,那么头指针理应指向的就是小数,而尾指针理应指向的就是大数,故当头指针指的是大数且尾指针指的是小数的时候就不正常,此时就当交换。

        因此,我们的做法是维护两个指针i和j,一个指针指向数组的第一个数的前一个位置,我们称之为后指针i,向右移动;一个指针指向数组第一个数, 称之为前指针j,也向右移动,且前指针j先向右移动。如果前指针j指向的数字是奇数,则令i指针向右移动一位,然后交换i和j指针所各自指向的数字。

        如果你能很快想到类似快排 partition 的解决方案,说明你理解了快速排序。

        三、举一反三——是金子,你就应该发光

        奇偶调序问题我们顺利用 partition 思想在O(n)的复杂度下解决了战斗,恩,我们获取思想的能力还是不错的。接下来,我们再来一瓶:荷兰国旗问题。

        拿破仑席卷欧洲大陆之后,代表自由,平等,博爱的竖色三色旗也风靡一时。荷兰国旗就是一面三色旗(只不过是横向的),自上而下为红白蓝三色。

说一说程序员“举一反三”的能力

        该问题本身是关于三色球排序和分类的,由荷兰科学家 Dijkstra 提出。由于问题中的三色小球有序排列后正好分为三类,Dijkstra 就想象成他母国的国旗,于是问题也就被命名为荷兰旗问题(Dutch National Flag Problem)。

        问题的正规描述:

        有n个红白蓝三种不同颜色的小球,乱序排列在一起,请通过两两交换任意两个球,使得从左至右,依次是一些红球、一些白球、一些蓝球。

        分析与解法:

        首先,你看到在问题,可能会无从下手。但如果给你提示,让你尽量往快排思想上靠拢呢?

        我们知道,快速排序依托于一个 partition 分治过程,在每一趟排序的过程中,选取的主元都会把整个数组排列成一大一小的部分,那我们是否可以借鉴 partition 过程设定三个指针完成重新排列,使得所有球排列成三个不同颜色的球呢?

        由此,我们得到此问题的一个解决方法:

        通过前面的分析得知,这个问题类似快排中 partition 过程,只是需要用到三个指针:一个前指针 begin,一个中指针 current,一个后指针 end,current 指针遍历整个数组序列,当

  1. current 指针所指元素为 0 时,与 begin 指针所指的元素交换,而后 current++,begin++ ;
  2. current 指针所指元素为 1 时,不做任何交换(即球不动),而后 current++ ;
  3. current 指针所指元素为 2 时,与 end 指针所指的元素交换,而后,current 指针不动,end– 。

        为什么上述第 3 点中,current 指针所指元素为 2 时,与 end 指针所指元素交换之后,current 指针不能动呢?因为第三步中 current 指针所指元素与 end 指针所指元素交换之前,如果 end 指针之前指的元素是0,那么与 current 指针所指元素交换之后,current 指针此刻所指的元素是 0,此时,current 指针能动么?不能动,因为如上述第 1 点所述,如果 current 指针所指的元素是0,还得与 begin 指针所指的元素交换。

        说这么多,你可能不甚明了,直接引用下 gnuhpc 的图,就一目了然了:

说一说程序员“举一反三”的能力

说一说程序员“举一反三”的能力

        通过以上几个问题,你现在可以给自己“举一反三”的能力打个分了。

        如果你觉得你懂了快速排序算法,在给出提示的情况下,却没能想到荷兰国旗问题的相关解法,甚至奇偶调序问题都想不到相关的解法,你应该问问自己:你真的懂了吗?

        不管你懂不懂,我反正不懂!

        全文大部分内容整理自《程序员编程艺术》一书部分章节。

 
来自: www.cricode.com