题目描述
输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下4 X 4矩阵: 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.
示例1:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
思路
1.这道题比较麻烦的就是边界值的界定,我们可以设置四个点的坐标来标识左上、左下、右上以及右下的位置。
2.我们可以通过二维数组的长和宽相乘获得数组内元素的个数,若数组内的元素没被遍历完成,就一直按照 左上-->右上,右上-->右下,右下-->左下,左下-->左上的顺序遍历下去即可。
Java代码实现
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<>();
if(matrix.length == 0)
return res;
int row = matrix.length-1;
int col = matrix[0].length-1;
int count = matrix.length*matrix[0].length;
int[] leftUp = new int[]{0,0};
int[] rightUp = new int[]{0,col};
int[] leftDown= new int[]{row,0};
int[] rightDown = new int[]{row,col};
while(count>0){
//从 左上 往 右上 变的是纵坐标
for (int i = leftUp[1]; i <= rightUp[1] && count>0; i++) {
res.add(matrix[leftUp[0]][i]);
count--;
}
//左上 和 右上的横坐标+1
leftUp[0]++;
rightUp[0]++;
//从 右上 往 右下 变的是横坐标
for (int i = rightUp[0]; i <= rightDown[0] && count>0; i++) {
res.add(matrix[i][rightUp[1]]);
count--;
}
//右上 和 右下的纵坐标 -1
rightUp[1]--;
rightDown[1]--;
//从 右下 往 左下 变的是纵坐标
for (int i = rightDown[1]; i >= leftDown[1]&& count>0; i--) {
res.add(matrix[leftDown[0]][i]);
count--;
}
//右下 和 左下的 横坐标 -1
rightDown[0]--;
leftDown[0]--;
//从 左下 往 左上 变的是横坐标
for (int i = leftDown[0]; i >=leftUp[0] && count>0; i--) {
res.add(matrix[i][leftDown[1]]);
count--;
}
//左下 和 左上的 纵坐标 +1
leftDown[1]++;
leftUp[1]++;
}
return res;
}
Golang代码实现
func spiralOrder(matrix [][]int) []int {
if len(matrix) == 0{
return make([]int,0)
}
sum := len(matrix)*len(matrix[0])
res := make([]int,sum)
count := 0
//左上角坐标
leftUp := [2]int{0,0}
//右上角坐标
rightUp := [2]int{0,len(matrix[0])-1}
//左下角坐标
leftDown := [2]int{len(matrix)-1,0}
//右下角坐标
rightDown := [2]int{len(matrix)-1,len(matrix[0])-1}
for count < sum {
//从左上角到右上角
for i:=leftUp[1];i<=rightUp[1]&&count<sum;i++{
res[count] = matrix[leftUp[0]][i]
count++
}
leftUp[0]++
rightUp[0]++
//从右上角到右下角
for i:=rightUp[0];i<=rightDown[0]&&count<sum;i++{
res[count] = matrix[i][rightDown[1]]
count++
}
rightUp[1]--
rightDown[1]--
//从右下角到左下角
for i:=rightDown[1];i>=leftDown[1] && count<sum; i--{
res[count] = matrix[rightDown[0]][i]
count++
}
leftDown[0]--
rightDown[0]--
//从左下角到左上角
for i:=leftDown[0];i>=leftUp[0] && count<sum;i-- {
res[count] = matrix[i][leftDown[1]]
count++
}
leftUp[1]++
leftDown[1]++
}
return res
}
有疑问加站长微信联系(非本文作者)