題目：輸入一個矩陣，按照從外向里以順時針的順序依次打印出每一個數字。

例如：如果輸入如下矩陣：

1??????????????2??????????????3??????????????4
5??????????????6??????????????7??????????????8
9??????????????10???????????11???????????12
13???????????14???????????15???????????16

則依次打印出數字1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10。

分析：第一次看到這個題目的時候，覺得這個題目很簡單，完全不需要用到數據結構或者算法的知識，因此沒有興趣做這道題。后來聽到包括Autodesk、EMC在內的多家公司在面試或者筆試里采用過這道題，于是想這么多家公司用它來檢驗一個程序員的編程功底總是有原因的，于是決定自己寫一遍試一下。真正寫一遍才發現，要完整寫出這道題的代碼，還真不是件容易的事情。

????????????????解決這道題的難度在于代碼中會包含很多個循環，而且還有多個邊界條件需要判斷。如果在把問題考慮得很清楚之前就開始寫代碼，不可避免地會越寫越混亂。因此解決這個問題的關鍵，在于先要形成清晰的思路，并把復雜的問題分解成若干個簡單的問題。下面分享我分析這個問題的過程。

????????????????通常當我們遇到一個復雜的問題的時候，我們可以用圖形幫助我們思考。由于我們是以從外圈到內圈的順序依次打印，我們在矩陣中標注一圈作為我們分析的目標。在下圖中，我們設矩陣的寬度為columns，而其高度為rows。我們我們選取左上角坐標為(startX, startY)，右下角坐標為(endX, endY)的一個圈來分析。

?	?	?	?	?	?
?	startX, startY	?	?	?	?
?	?	?	?	?	?
?	?	?	?	?	?
?	?	?	?	endX, endY	?
?	?	?	?	?	?

由于endX和endY可以根據startX、startY以及columns、rows來求得，因此此時我們只需要引入startX和startY兩個變量。我們可以想象有一個循環，在每一次循環里我們從(startX, startY)出發按照順時針打印數字。

接著我們分析這個循環結束的條件。對一個5×5的矩陣而言，最后一圈只有一個數字，對應的坐標為(2, 2)。我們發現5 > 2 * 2。對一個6×6的矩陣而言，最后一圈有四個數字，對應的坐標仍然為(2, 2)。我們發現6 > 2 * 2依然成立。于是我們可以得出，讓循環繼續的條件是columns > startX * 2 && rows > startY * 2。有了這些分析，我們就可以寫出如下的代碼：

void PrintMatrixClockwisely(int** numbers, int columns, int rows) {if(numbers == NULL || columns <= 0 || rows <= 0)return;int startX = 0;int startY = 0;while(columns > startX * 2 && rows > startY * 2){PrintMatrixInCircle(numbers, columns, rows, startX, startY);++startX;++startY;} }

接下來我們分析如何在PrintMatrixInCircle中按照順時針的順序打印一圈的數字。如同在圖中標注的那樣，我們可以分四步來打印：第一步是從左到右打印一行（上圖中黃色區域），第二步是從上到下打印一列（上圖中綠色區域），第三步從右到左打印一行（上圖中藍色區域），最后一步是從下到上打印一列（上圖中紫色區域）。也就是我們把打印一圈數字這個問題，分解成四個子問題。我們可以為每個子問題定義一個函數。四個步驟對應的函數名稱我們分別定義為：PrintARowIncreasingly，PrintAColumnIncreasingly，PrintARowDecreasingly和PrintAColumnDecreasingly。

現在我們暫時不考慮如何去實現這四個函數，而是先考慮我們需要分別給這些函數傳入哪些參數。第一步打印一行時，所有的數字的行號是固定的（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,int startX, int startY) {int endX = columns - 1 - startX;int endY = rows - 1 - startY;PrintARowIncreasingly(numbers, columns, rows, startY, startX, endX);if(startY < endY)PrintAColumnIncreasingly(numbers, columns, rows, endX, startY + 1, endY);if(startX < endX && startY < endY)PrintARowDecreasingly(numbers, columns, rows, endY, endX - 1, startX);if(startX < endX && startY < endY - 1)PrintAColumnDecreasingly(numbers, columns, rows, startX, endY - 1, startY + 1); }

接下來我們考慮如何打印一行或者一列。這對我們來說不是一件很難的事情。以函數PrintARowIncreasingly為例，我們只需要一個循環，把行號為startY，列號從startX到endX的所有數字依次從數組中取出來并逐個打印就行了，對應的代碼是：

void PrintARowIncreasingly(int** numbers, int columns, int rows,int y, int firstX, int lastX) {for(int i = firstX; i <= lastX; ++i){int number = *(*(numbers + y) + i);printf("%d\t", number);} }

剩下的三個函數與此類似，代碼依次如下：

void PrintAColumnIncreasingly(int** numbers, int columns, int rows,int x, int firstY, int lastY) {for(int i = firstY; i <= lastY; ++i){int number = *(*(numbers + i) + x);printf("%d\t", number);} } void PrintARowDecreasingly(int** numbers, int columns, int rows,int y, int firstX, int lastX) {for(int i = firstX; i >= lastX; --i){int number = *(*(numbers + y) + i);printf("%d\t", number);} } void PrintAColumnDecreasingly(int** numbers, int columns, int rows,int x, int firstY, int lastY) {for(int i = firstY; i >= lastY; --i){int number = *(*(numbers + i) + x);printf("%d\t", number);} }

?

本文已經收錄到《劍指Offer——名企面試官精講典型編程題》一書中，有改動，書中的分析講解更加詳細。歡迎關注。

本題已被九度Online Judge系統收錄，歡迎讀者移步到http://ac.jobdu.com/hhtproblems.php在線測試自己的代碼。

博主何海濤對本博客文章享有版權。網絡轉載請注明出處http://zhedahht.blog.163.com/。整理出版物請和作者聯系。

總結

以上是生活随笔為你收集整理的程序员面试题精选100题(51)-顺时针打印矩阵[算法]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。