程序员面试题精选100题(51)-顺时针打印矩阵[算法]

面试题 时间:2019-09-22 手机网站
                ++startX;

                ++startY;

        }

}

接下来我们分析如何在PrintMatrixInCircle中按照顺时针的顺序打印一圈的数字。如同在图中标注的那样,我们可以分四步来打印:第一步是从左到右打印一行(上图中黄色区域),第二步是从上到下打印一列(上图中绿色区域),第三步从右到左打印一行(上图中蓝色区域),最后一步是从下到上打印一列(上图中紫色区域)。也就是我们把打印一圈数字这个问题,分解成四个子问题。我们可以为每个子问题定义一个函数。四个步骤对应的函数名称我们分别定义为:PrintARowIncreasinglyPrintAColumnIncreasinglyPrintARowDecreasinglyPrintAColumnDecreasingly

现在我们暂时不考虑如何去实现这四个函数,而是先考虑我们需要分别给这些函数传入哪些参数。第一步打印一行时,所有的数字的行号是固定的(startY),不同数字的列号不同。我们需要传入一个起始列号(startX)和终止列号(endX)。第二步打印一列时,所有的数字的列号是固定的,不同的数字的行号不同。我们需要传入一个起始行号(startY + 1)和一个终止行号(endY)。第三步和第四步和前面两步类似,读者可以自己分析。

接下来我们需要考虑特殊情况。并不是所有数字圈都需要四步来打印。比如当一圈退化成一行的时候,也就是startY等于endY的时候,我们只需要第一步就把所有的数字都打印完了,其余的步骤都是多余的。因此我们需要考虑第二、三、四步打印的条件。根据前面我们分析,不难发现打印第二步的条件是startY < endY。对于第三步而言,如果startX等于endX,也就是这一圈中只有一列数字,那么所有的数字都在第二步打印完了;如果startY等于endY,也就是这一圈中只有一行数字,那么所有的数字都在第一步打印完了。因此需要打印第三步的条件是startX < endX && startX < endY。第四步最复杂,首先startX要小于endX,不然所有的数字都在一列,在第二步中就都打印完了。另外,这个圈中至少要有三行数字。如果只有一行数字,所有数字在第一步中打印完了;如果只有两行数字,所有数字在第一步和第三步也都打印完了。因此打印第四步需要的条件是startY < endY – 1

有了前面的分析,我们就能写出PrintMatrixInCircle的完整代码如下:

void PrintMatrixInCircle(int** numbers, int columns, int rows,