劍指offer29——順時針列印矩陣（力扣54：螺旋矩陣）：思路分享
思路決議：
找到左上角和右下角，就能夠將一圈的數字列印出來！列印完一圈后，只需要左上角的坐標+1，右下角的坐標-1，回圈即可
回圈判斷條件就是左上角的坐標<=右上角的坐標
步驟分析：
- 找到左上角和右下角的坐標，設為
(tR,tC)，(dR,dC) - 判斷二維陣列是否為空，然后進入回圈
- 回圈終止條件：是左上角和右上角重合
- 進入回圈判斷是否為同一條直線，然后按順序列印”上、右、下、左“四條邊，每次回圈結束，都要改變起始坐標
注意！
- 每列（行）的轉折點交給下一行（列）處理，不然會出現陣列越界
- 如果是用陣列接收列印結果的話，要注意陣列的索引，也就是全域變數
count，此時不能將列印代碼封裝到while回圈中，count的值會覆寫
復雜度分析：
- 時間復雜度為
O(mn)，因為將每個元素都訪問了一遍 - 空間復雜度為
O(1)，因為不需要額外空間，陣列res是題目中規定的
Java代碼如下：
class Solution {
public int[] spiralOrder(int[][] matrix) {
//如果二維陣列為空，回傳空陣列即可
if(matrix.length==0 || matrix==null || matrix[0].length==0) {
return new int[0];
}
//找到左上角和右上角
int tR=0, tC=0;
int dR=matrix.length-1, dC=matrix[0].length-1;
//定義結果陣列
int[] res=new int[(dR+1) * (dC+1)];
//陣列索引
int count=0;
while(tR<=dR && tC<=dC) {
//判斷是否在同一行或者同一列
if(tR==dR) {
for(int i=tC;i<=dC;i++) {
res[count++]=matrix[tR][i];
}
} else if(tC==dC) {
for(int i=tR;i<=dR;i++) {
res[count++]=matrix[i][tC];
}
} else {
int curR=tR, curC=tC;
while(curC<dC) {
res[count++]=matrix[tR][curC++];
}
while(curR<dR) {
res[count++]=matrix[curR++][dC];
}
while(curC>tC) {
res[count++]=matrix[dR][curC--];
}
while(curR>tR) {
res[count++]=matrix[curR--][tC];
}
}
tR++;
tC++;
dR--;
dC--;
}
return res;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/244324.html
標籤：其他
下一篇：E.牛牛的反函式(規律,貪心)