二維矩陣按圈遍歷（順時針 or 逆時針）遍歷

下面的題目的主要考察點都是，二維數組從左上角開始順時針（或者逆時針）按圈遍歷數組的過程。順時針按圈遍歷的過程如下：

對于每一圈，分為四條邊，循環遍歷就好。這時，對于四個角的元素的處理，可以將四條邊的遍歷分為以下兩種情況：

• 第一種：每條邊都從對應一角開始，遍歷對應邊的時候，最后一個元素留給下一條邊；比如第一條綠色的邊，最后一個元素就沒有訪問；第二條黃色的邊就從左上角元素開始，相應的最左下角的元素沒有訪問；以此類推；
  代碼實現（C++）：

        //count表示訪問了的元素個數，控制遍歷完數組沒有while(count <= n*n){//i，j是行、列的下標，每次總是從[0,0]，[1,1]開始一圈循環int i = p;int j = p;//每圈最上面一條邊的遍歷         while(j < n - 1 - p){//因為最一個元素[i][n-1-p]留給下一條邊，因此這里不取等ans[i][j++] = count++;}//每圈最右邊的一條邊的遍歷while(i < n - 1 - p){//因為最一個元素[n-1-p][j]留給下一條邊，因此這里不取等ans[i++][j] = count++;}//每圈最下面一條邊的遍歷while(j > p){//因為最后一個元素[i][p]留給下一條邊，因此這里不取等ans[i][j--] = count++;}//每圈最左邊的一條邊的遍歷while(i > p){//因為[p][p]就是這一圈的起始點，在第一條邊就遍歷過了，所以這里取等ans[i--][j] = count++;}p++;}

• 第二種：遍歷每一條邊時，就將該邊所有未被訪問的元素全部遍歷；比如第一條綠色的，最后一個元素就訪問了；然后第二條邊黃色的就對應列的第二個開始，因為第一個已經被訪問了；之后的邊以此類推；
  代碼實現（C++）：

        //count控制遍歷完了沒有while(count <= n*n){   //遍歷最上邊的一條邊        for(int i = left; i <= right ; i++){ans[top][i] = count++;}//遍歷完后top++top++;//遍歷最右邊的邊for(int i = top; i <= bottom; i++){ans[i][right] = count++;}//遍歷完后right--right--;//遍歷最下邊的邊for(int i = right; i >= left ;i--){ans[bottom][i] = count++;}//遍歷完后bottom--bottom--;//遍歷最左邊一條邊for(int i = bottom; i >= top; i--){ans[i][left] = count++;}//遍歷完后left++left++;}

59. 旋轉矩陣Ⅱ

螺旋矩陣 II
題目內容如下：

注意點是n*n的正方形矩陣，行列數量相同。只要按照前面提到的順時針訪問數組的過程中，給每個位置遞增賦值就好。按圈遍歷的過程中，需要循環遍歷多少次呢？答案是(n+1)/2次。

但是按照上面提到的第一種俺圈遍歷的過程中：

• n為偶數時，每次減少2行，2 列，最后剛好遍歷完；
• n為奇數時，最后一次只有單獨一個，因為每條邊的最后一個元素都留給下一條邊了，所以實際上沒有哪條邊去遍歷了。比如n=5，p=2時，i=2，j=2，n-1-p=2，由于i=j=p=n-1-p，第一種代碼提到的四種循環條件都不滿足。所以在最后要單獨給這個位置賦值。代碼如下（C++）：

class Solution {
public:vector<vector<int>> generateMatrix(int n) {int count = 1;int i, j, p;vector<vector<int>> ans(n,vector<int>(n));//因為n為奇數的最后一圈在最后單獨賦值，所以這里p<n/2就好for(int p = 0; p < n/2; p++){i = p;j = p;         while(j < n - 1 - p){ans[i][j++] = count++;}while(i < n - 1 - p){ans[i++][j] = count++;}while(j > p){ans[i][j--] = count++;}while(i > p){ans[i--][j] = count++;}}//n為奇數時，最后一個位置（最中間）單獨賦值if( n%2 != 0){ans[n/2][n/2] = count;}return ans;}
}; 

對于第二種按圈遍歷的過程，因為用top//bottom//left//right來控制，最后中間位置的能夠遍歷到，不需要額外的處理，代碼如下（C++）：

class Solution {
public:vector<vector<int>> generateMatrix(int n) {        vector<vector<int>> ans(n,vector<int>(n));int left = 0, right = n - 1;int top = 0, bottom = n -1;int count = 1;while(count <= n*n){int i;for(i = left; i <= right ; i++){ans[top][i] = count++;}top++;for(i = top; i <= bottom; i++){ans[i][right] = count++;}right--;for(i = right; i >= left ;i--){ans[bottom][i] = count++;}bottom--;for(i = bottom; i >= top; i--){ans[i][left] = count++;}left++;}return ans;}
}; 

54. 旋轉矩陣

54. 旋轉矩陣
題意如下：
跟上一題不同的點在于，矩陣由nn變成了==mn==，m和n不一定相等，即現在的矩陣可能不再是正方形的了。那么根據m（行數）///n（偶數）是奇數還是偶數？大小關系可以分為以下七種情況：

分析這7種情況，得出結論，只要滿足如下兩種情況之一，最后就有需要單獨處理的：

• m<n并且m是奇數（不管n是奇是偶），最終會多出來一行（因為m行數更小，行先結束圈的遍歷，但是列還有更多的，所以多出來一行）；
• n<m并且n是奇數（不管m是奇是偶），最終會多出來一列（因為n列數更小，列先結束圈的遍歷，但是行還有很多，所以多出來一列）；
  （m=n同為奇數的情況可以歸為上述任意一種）。
  代碼實現的過程，就是最終會判斷一下是否出現上面的情況，然后單獨處理這一行///這一列就好，代碼如下：

class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {int step_i = 0, step_j = 0, index = 0;int m = matrix.size(), n = matrix[0].size();vector<int> ans(m*n);//與上一題代碼基本一致，只是<m/2和<n/2需要單獨判斷while(step_i < m/2 && step_j < n/2){int i = step_i;int j = step_j;for(; j < n - 1 -step_j; j++){ans[index++] = matrix[i][j];}for(; i < m - 1 - step_i; i++){ans[index++] = matrix[i][j];}for(; j > step_j; j--){ans[index++] = matrix[i][j];}for(; i > step_i ;i--){ans[index++] = matrix[i][j];}step_i++;step_j++;}//行是奇數并且m<n，剩下一行if(m%2 != 0 && step_i == m/2){for(int j = step_j; j < n - step_j; j++)ans[index++] = matrix[step_i][j];}//列是奇數并且n<m，剩下一列else if(n%2 != 0 && step_j == n/2){for(int i = step_i; i < m -step_i; i++ )ans[index++] = matrix[i][step_j];} return ans;    }
};

如果用第二種按圈遍歷的方法，更簡單，只是在大循環內依次進行的四個小循環，需要在最后兩個循環添加額外的循環條件：

class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {int m = matrix.size(), n = matrix[0].size();vector<int> ans(m*n);int left = 0, right = n - 1;int top = 0, bottom = m - 1;int index = 0;while(index < m*n){for(int i = left; i <= right; i++){ans[index++] = matrix[top][i];}top++;for(int i = top; i <= bottom; i++){ans[index++] = matrix[i][right];}right--;//需要添加額外的條件 index < m*n (根據實際題目要求選擇對應的約束條件for(int i = right; i >=left && index < m*n; i--){ans[index++] = matrix[bottom][i];}bottom--;//需要添加額外的條件index < m*n (根據實際題目要求選擇對應的約束條件for(int i = bottom; i >= top && index < m*n; i--){ans[index++] = matrix[i][left];}left++;}return ans;}
};

為什么要添加這兩個？請看下例：

如果不在內層的四個循環的后兩個中添加額外的限制，就會出現多遍歷的情況。

劍指 Offer 29. 順時針打印矩陣

劍指 Offer 29. 順時針打印矩陣
和54是一樣的題目，只是注意m和n可能等于0。