题目描述
输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下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 }