按螺旋顺序打印二维数组
如何以螺旋顺序打印5×5的二维数组？
是否有任何公式，以便我可以按螺旋顺序打印任何大小的数组？
我们的想法是将matrix看作一系列图层，右上图层和左下图层。 要螺旋打印matrix，我们可以从这些matrix中剥离图层，打印已剥离的部分，recursion地调用左侧的部分。 当我们没有更多的图层打印时，recursion就终止了。
inputmatrix：
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 1 剥去右上层后：
1 2 3 4 8 5 6 7 2 9 0 1 6 3 4 5 1 7 8 9
从子matrix剥离左下层之后：
6 7 5 0 1 9 4 5 3 7 8 9
从子matrix剥去右上层之后：
6 7 1 0 5 4
从子matrix剥离左下层之后：
0 4
recursion终止。
Cfunction：
// function to print the top-right peel of the matrix and // recursively call the print bottom-left on the submatrix. void printTopRight(int a[][COL], int x1, int y1, int x2, int y2) { int i = 0, j = 0; // print values in the row. for(i = x1; i<=x2; i++) { printf("%d ", a[y1][i]); } // print values in the column. for(j = y1 + 1; j <= y2; j++) { printf("%d ", a[j][x2]); } // see if more layers need to be printed. if(x2-x1 > 0) { // if yes recursively call the function to // print the bottom left of the sub matrix. printBottomLeft(a, x1, y1 + 1, x2-1, y2); } } // function to print the bottom-left peel of the matrix and // recursively call the print top-right on the submatrix. void printBottomLeft(int a[][COL], int x1, int y1, int x2, int y2) { int i = 0, j = 0; // print the values in the row in reverse order. for(i = x2; i>=x1; i--) { printf("%d ", a[y2][i]); } // print the values in the col in reverse order. for(j = y2 - 1; j >= y1; j--) { printf("%d ", a[j][x1]); } // see if more layers need to be printed. if(x2-x1 > 0) { // if yes recursively call the function to // print the top right of the sub matrix. printTopRight(a, x1+1, y1, x2, y2-1); } } void printSpiral(int arr[][COL]) { printTopRight(arr,0,0,COL-1,ROW-1); printf("\n"); }
Ideone Link
- stream行顶行
- 转置并翻转（与逆时针旋转90度相同）
- 转到1
Python代码：
import itertools arr = [[1,2,3,4], [12,13,14,5], [11,16,15,6], [10,9,8,7]] def transpose_and_yield_top(arr): while arr: yield arr[0] arr = list(reversed(zip(*arr[1:]))) print list(itertools.chain(*transpose_and_yield_top(arr)))
我看到没有人只使用一个for loop ， 没有在代码中recursion ，所以我想贡献。
这个想法是这样的：
想象一下，有一只乌龟站在点（0,0），也就是左上angular，向东（向右）
它会继续前进 ，每次看到一个标志，乌龟都会右转
所以如果我们把龟（0,0）的龟放在右侧，如果我们在适当的地方放置这些龟，龟就会以螺旋的方式穿过arrays。
现在的问题是：“把标志放在哪里？”
让我们看看我们应该把标志（用＃标记，用O标记）：
对于一个看起来像这样的网格： OOOO OOOO OOOO OOOO 我们把这样的标志： OOO＃ ＃O＃O O＃＃O ＃OO＃ 对于一个看起来像这样的网格： OOO OOO OOO OOO 我们把这样的标志： OO＃ ＃＃ O＃O ＃O＃ 而对于一个像这样的网格： OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO 我们把这样的标志： OOOOOO＃ ＃OOOO＃O O＃OO＃OO O＃OOO＃O ＃OOOOO＃
我们可以看到，除非点在左上angular，否则标志是距最近的水平边界和最近的垂直边界的距离相同的点的位置 ，而对于左上angular的部分， 距离上边框比左边框的距离多一点 ，如果点是水平居中的，则优先给予右上angular;如果点是垂直居中的，则优先给予左上angular。
（ curRow和height-1-curRow ）的最小值，然后是（ curCol和width-1-curCol ） width-1-curCol ，比较它们是否相同。 但是我们需要考虑左上angular的情况，也就是当最小值是curRow和curCol 。 在这种情况下，我们相应地减小垂直距离。
这里是C代码：
#include <stdio.h> int shouldTurn(int row, int col, int height, int width){ int same = 1; if(row > height-1-row) row = height-1-row, same = 0; // Give precedence to top-left over bottom-left if(col >= width-1-col) col = width-1-col, same = 0; // Give precedence to top-right over top-left row -= same; // When the row and col doesn't change, this will reduce row by 1 if(row==col) return 1; return 0; } int directions[4][2] = {{0,1},{1,0},{0,-1},{-1,0}}; void printSpiral(int arr[4][4], int height, int width){ int directionIdx=0, i=0; int curRow=0, curCol=0; for(i=0; i<height*width; i++){ printf("%d ",arr[curRow][curCol]); if(shouldTurn(curRow, curCol, height, width)){ directionIdx = (directionIdx+1)%4; } curRow += directions[directionIdx][0]; curCol += directions[directionIdx][1]; } printf("\n"); } int main(){ int arr[4][4]= {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}}; printSpiral(arr, 4, 4); printSpiral(arr, 3, 4); }
哪些产出：
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 1 2 3 4 8 12 11 10 9 5 6 7
以下是三个有趣的方法
-
以螺旋方式阅读可以被看作是一条蛇向边界移动，并打开边界或本身（我发现它优雅，最有效的是一个单一的循环N迭代）
ar = [ [ 0, 1, 2, 3, 4], [15, 16, 17, 18, 5], [14, 23, 24, 19, 6], [13, 22, 21, 20, 7], [12, 11, 10, 9, 8]] def print_spiral(ar): """ assuming a rect array """ rows, cols = len(ar), len(ar[0]) r, c = 0, -1 # start here nextturn = stepsx = cols # move so many steps stepsy = rows-1 inc_c, inc_r = 1, 0 # at each step move this much turns = 0 # how many times our snake had turned for i in range(rows*cols): c += inc_c r += inc_r print ar[r][c], if i == nextturn-1: turns += 1 # at each turn reduce how many steps we go next if turns%2==0: nextturn += stepsx stepsy -= 1 else: nextturn += stepsy stepsx -= 1 # change directions inc_c, inc_r = -inc_r, inc_c print_spiral(ar)
输出：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
-
recursion的方法是打印外层，并为内部矩形调用相同的函数，例如
def print_spiral(ar, sr=0, sc=0, er=None, ec=None): er = er or len(ar)-1 ec = ec or len(ar[0])-1 if sr > er or sc > ec: print return # print the outer layer top, bottom, left, right = [], [], [], [] for c in range(sc,ec+1): top.append(ar[sr][c]) if sr != er: bottom.append(ar[er][ec-(c-sc)]) for r in range(sr+1,er): right.append(ar[r][ec]) if ec != sc: left.append(ar[er-(r-sr)][sc]) print " ".join([str(a) for a in top + right + bottom + left]), # peel next layer of onion print_spiral(ar, sr+1, sc+1, er-1, ec-1)
最后这里是一个小的片段来做到这一点，效率不高，但有趣:)，基本上它打印最上面一排，并逆时针旋转整个矩形，重复
def print_spiral(ar): if not ar: return print " ".join(str(a) for a in ar[0]), ar = zip(*[ reversed(row) for row in ar[1:]]) print_spiral(ar)
这个程序适用于任何n * nmatrix
public class circ { public void get_circ_arr (int n,int [][] a) { int z=n; { for (int i=0;i<n;i++) { for (int l=z-1-i;l>=i;l--) { int k=i; System.out.printf("%d",a[k][l]); } for (int j=i+1;j<=z-1-i;j++) { int k=i; { System.out.printf("%d",a[j][k]); } } for (int j=i+1;j<=zi-1;j++) { int k=z-1-i; { System.out.printf("%d",a[k][j]); } } for (int j=z-2-i;j>=i+1;j--) { int k=zi-1; { System.out.printf("%d",a[j][k]); } } } } } }
希望它有帮助
当我学习Ruby时，我迷上了这个问题。 这是我能做的最好的事情：
def spiral(matrix) matrix.empty? ? [] : matrix.shift + spiral(matrix.transpose.reverse) end
您可以通过回顾本文中的修订内容来查看一些其他解决scheme。 另外，如果你按照链接返回给我的要求，你会发现一些其他聪明的解决scheme。 真正有趣的问题，可以在多个优雅的方式来解决 – 特别是在Ruby中。
JavaScript解决scheme：
var printSpiral = function (matrix) { var i; var top = 0; var left = 0; var bottom = matrix.length; var right = matrix[0].length; while (top < bottom && left < right) { //print top for (i = left; i < right; i += 1) { console.log(matrix[top][i]); } top++; //print right column for (i = top; i < bottom; i += 1) { console.log(matrix[i][right - 1]); } right--; if (top < bottom) { //print bottom for (i = right - 1; i >= left; i -= 1) { console.log(matrix[bottom - 1][i]); } bottom--; } if (left < right) { //print left column for (i = bottom - 1; i >= top; i -= 1) { console.log(matrix[i][left]); } left++; } } };
一种解决scheme涉及右，左，上，下方向及其相应的限制（指数）。 一旦打印第一行，并且方向改变（从右向下），通过递增上限来丢弃该行。 一旦最后一列被打印，并且方向改变到左边，通过递减右手限制来丢弃该列…可以在不言自明的C代码中看到细节。
#include <stdio.h> #define N_ROWS 5 #define N_COLS 3 void print_spiral(int a[N_ROWS][N_COLS]) { enum {up, down, left, right} direction = right; int up_limit = 0, down_limit = N_ROWS - 1, left_limit = 0, right_limit = N_COLS - 1, downcount = N_ROWS * N_COLS, row = 0, col = 0; while(printf("%d ", a[row][col]) && --downcount) if(direction == right) { if(++col > right_limit) { --col; direction = down; ++up_limit; ++row; } } else if(direction == down) { if(++row > down_limit) { --row; direction = left; --right_limit; --col; } } else if(direction == left) { if(--col < left_limit) { ++col; direction = up; --down_limit; --row; } } else /* direction == up */ if(--row < up_limit) { ++row; direction = right; ++left_limit; ++col; } } void main() { int a[N_ROWS][N_COLS] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}; print_spiral(a); }
链接testing和下载
。
给定一个字符matrix，实现一个按以下顺序打印所有字符的方法：首先是外部圆，然后是下一个，依此类推。
public static void printMatrixInSpiral(int[][] mat){ if(mat.length == 0|| mat[0].length == 0){ /* empty matrix */ return; } StringBuffer str = new StringBuffer(); int counter = mat.length * mat[0].length; int startRow = 0; int endRow = mat.length-1; int startCol = 0; int endCol = mat[0].length-1; boolean moveCol = true; boolean leftToRight = true; boolean upDown = true; while(counter>0){ if(moveCol){ if(leftToRight){ /* printing entire row left to right */ for(int i = startCol; i <= endCol ; i++){ str.append(mat[startRow][i]); counter--; } leftToRight = false; moveCol = false; startRow++; } else{ /* printing entire row right to left */ for(int i = endCol ; i >= startCol ; i--){ str.append(mat[endRow][i]); counter--; } leftToRight = true; moveCol = false; endRow--; } } else { if(upDown){ /* printing column up down */ for(int i = startRow ; i <= endRow ; i++){ str.append(mat[i][endCol]); counter--; } upDown = false; moveCol = true; endCol--; } else { /* printing entire col down up */ for(int i = endRow ; i >= startRow ; i--){ str.append(mat[i][startCol]); counter--; } upDown = true; moveCol = true; startCol++; } } } System.out.println(str.toString()); }
二维N×Nmatrix是方阵
理念：
我们必须在四个不同的方向上进行遍历，像螺旋一样。 一旦一层螺旋结束，我们必须遍历内部matrix。 总的来说，我们需要5个循环，4个循环像螺旋和1个循环遍历层。
public void printSpiralForm(int[][] a, int length) { for( int i = 0 , j = length-1 ; i < j ; i++ , j-- ) { for( int k = i ; k < j ; k++ ) { System.out.print( a[i][k] + " " ) ; } for( int k = i ; k < j ; k++ ) { System.out.print(a[k][j] + " "); } for( int k = j ; k > i ; k-- ) { System.out.print(a[j][k] + " ") ; } for( int k = j ; k > i ; k-- ) { System.out.print( a[k][i] + " " ) ; } } if ( length % 2 == 1 ) { System.out.println( a[ length/2 ][ length/2 ] ) ; } }
这是我的实现：
public static void printMatrix(int matrix[][], int M, int N){ int level = 0; int min = (M < N) ? M:N; System.out.println(); while(level <= min/2){ for(int j = level; j < N - level - 1; j++){ System.out.print(matrix[level][j] + "\t"); } for(int i = level; i < M - level - 1; i++) { System.out.print(matrix[i][N - level - 1] + "\t"); } for(int j = N - level - 1; j > level; j--){ System.out.print(matrix[M - level - 1][j] + "\t"); } for(int i = M - level - 1; i > level; i-- ){ System.out.print(matrix[i][level] + "\t"); } level++; } }
int N = Integer.parseInt（args [0]）;
// create N-by-N array of integers 1 through N int[][] a = new int[N][N]; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) a[i][j] = 1 + N*i + j; // spiral for (int i = N-1, j = 0; i > 0; i--, j++) { for (int k = j; k < i; k++) System.out.println(a[j][k]); for (int k = j; k < i; k++) System.out.println(a[k][i]); for (int k = i; k > j; k--) System.out.println(a[i][k]); for (int k = i; k > j; k--) System.out.println(a[k][j]); } // special case for middle element if N is odd if (N % 2 == 1) System.out.println(a[(N-1)/2][(N-1)/2]); }
}
斜线顶行 – >移调 – >翻转 – >重复。
void slashTransposeFlip(int[][] m){ if( m.length * m[0].length == 1){ //only one element left System.out.print(m[0][0]); }else{ //print the top row for(int a:m[0]){System.out.print(a+" ");} //slash the top row from the matrix. int[][] n = Arrays.copyOfRange(m,1,m.length); int[][] temp = n; int rows = temp.length; int columns = temp[0].length; //invert rows and columns and create new array n = new int[columns][rows]; //transpose for(int x=0;x<rows;x++) for(int y=0;y<columns;y++) n[y][x] = temp[x][y]; //flipping time for (int i = 0; i < n.length / 2; i++) { int[] t = n[i]; n[i] = n[n.length - 1 - i]; n[n.length - 1 - i] = t; } //recursively call again the reduced matrix. slashTransposeFlip(n); } }
复杂性： 单遍历
O(n)
请让我添加复杂度为O(n) 单循环答案。 我发现在matrix的左右和左右运动中，行 – 主指数分别增加和减less一个。 同样，对于上下和上下遍历，增加和减lessn_cols 。 因此我为此做了一个algorithm。 例如，给定一个（3×5）matrix的行主索引输出是： 1,2,3,4,5,10,15,14,13,12,11,6,7,8,9 。
------->(+1) ^ 1 2 3 4 5 | (+n_cols) | 6 7 8 9 10 | (-n_cols) | 11 12 13 14 15 (-1)<-------
代码解决scheme
#include <iostream> using namespace std; int main() { // your code goes here bool leftToRight=true, topToBottom=false, rightToLeft=false, bottomToTop=false; int idx=0; int n_rows = 3; int n_cols = 5; int cnt_h = n_cols, cnt_v = n_rows, cnt=0; int iter=1; for (int i=0; i <= n_rows*n_cols + (n_rows - 1)*(n_cols - 1)/2; i++){ iter++; if(leftToRight){ if(cnt >= cnt_h){ cnt_h--; cnt=0; leftToRight = false; topToBottom = true; //cout << "Iter: "<< iter << " break_leftToRight"<<endl; }else{ cnt++; idx++; //cout << "Iter: "<< iter <<" idx: " << idx << " cnt: "<< cnt << " cnt_h: "<< cnt_h<< endl; cout<< idx << endl; } }else if(topToBottom){ if(cnt >= cnt_v-1){ cnt_v--; cnt=0; leftToRight = false; topToBottom = false; rightToLeft=true; //cout << "Iter: "<< iter << " break_topToBottom"<<endl; }else{ cnt++; idx+=n_cols; //cout << "Iter: "<< iter << " idx: " << idx << " cnt: "<< cnt << " cnt_v: "<< cnt_h<< endl; cout << idx <<endl; } }else if(rightToLeft){ if(cnt >= cnt_h){ cnt_h--; cnt=0; leftToRight = false; topToBottom = false; rightToLeft=false; bottomToTop=true; //cout << "Iter: "<< iter << " break_rightToLeft"<<endl; //cout<< idx << endl; }else{ cnt++; idx--; //cout << "Iter: "<< iter << " idx: " << idx << " cnt: "<< cnt << " cnt_h: "<< cnt_h<< endl; cout << idx <<endl; } }else if(bottomToTop){ if(cnt >= cnt_v-1){ cnt_v--; cnt=0; leftToRight = true; topToBottom = false; rightToLeft=false; bottomToTop=false; //cout << "Iter: "<< iter << " break_bottomToTop"<<endl; }else{ cnt++; idx-=n_cols; //cout << "Iter: "<< iter << " idx: " << idx << " cnt: "<< cnt << " cnt_v: "<< cnt_h<< endl; cout<< idx << endl; } } //cout << i << endl; } return 0; }
对于打印二维matrix，考虑matrix作为矩形和/或线的组合，其中将较小的矩形拟合为较大的矩形，采用matrix的边界来形成要打印的矩形，每一层中每次都从左上angular元素开始; 一旦完成了这里去为下一层较小的矩形，如果我没有一个矩形，那么它应该是行打印，水平或垂直。 我用代码matrixHTH粘贴了代码。
#include <stdio.h> int a[2][4] = { 1, 2 ,3, 44, 8, 9 ,4, 55 }; void print(int, int, int, int); int main() { int row1, col1, row2, col2; row1=0; col1=0; row2=1; col2=3; while(row2>=row1 && col2>=col1) { print(row1, col1, row2, col2); row1++; col1++; row2--; col2--; } return 0; } void print(int row1, int col1, int row2, int col2) { int i=row1; int j=col1; /* This is when single horizontal line needs to be printed */ if( row1==row2 && col1!=col2) { for(j=col1; j<=col2; j++) printf("%d ", a[i][j]); return; } /* This is when single vertical line needs to be printed */ if( col1==col2 && row1!=row2) { for(i=row1; j<=row2; i++) printf("%d ", a[i][j]); return; } /* This is reached when there is a rectangle to be printed */ for(j=col1; j<=col2; j++) printf("%d ", a[i][j]); for(j=col2,i=row1+1; i<=row2; i++) printf("%d ", a[i][j]); for(i=row2,j=col2-1; j>=col1; j--) printf("%d ", a[i][j]); for(j=col1,i=row2-1; i>row1; i--) printf("%d ", a[i][j]); }
这是我在Java中的实现：
public class SpiralPrint { static void spiral(int a[][],int x,int y){ //If the x and y co-ordinate collide, break off from the function if(x==y) return; int i; //Top-left to top-right for(i=x;i<y;i++) System.out.println(a[x][i]); //Top-right to bottom-right for(i=x+1;i<y;i++) System.out.println(a[i][y-1]); //Bottom-right to bottom-left for(i=y-2;i>=x;i--) System.out.println(a[y-1][i]); //Bottom left to top-left for(i=y-2;i>x;i--) System.out.println(a[i][x]); //Recursively call spiral spiral(a,x+1,y-1); } public static void main(String[] args) { int a[][]={{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}}; spiral(a,0,4); /*Might be implemented without the 0 on an afterthought, all arrays will start at 0 anyways. The second parameter will be the dimension of the array*/ } }
//shivi..coding is adictive!! #include<shiviheaders.h> #define R 3 #define C 6 using namespace std; void PrintSpiral(int er,int ec,int arr[R][C]) { int sr=0,sc=0,i=0; while(sr<=er && sc<=ec) { for(int i=sc;i<=ec;++i) cout<<arr[sr][i]<<" "; ++sr; for(int i=sr;i<=er;++i) cout<<arr[i][ec]<<" "; ec--; if(sr<=er) { for(int i=ec;i>=sc;--i) cout<<arr[er][i]<<" "; er--; } if(sc<=ec) { for(int i=er;i>=sr;--i) cout<<arr[i][sc]<<" "; ++sc; } } } int main() { int a[R][C] = { {1, 2, 3, 4, 5, 6}, {7, 8, 9, 10, 11, 12}, {13, 14, 15, 16, 17, 18} }; PrintSpiral(R-1, C-1, a); }
Java代码，如果有人感兴趣。
input ：
4
1 2 3 4
5 6 7 8
9 1 2 3
4 5 6 7
输出 ：1 2 3 4 8 3 7 6 5 4 9 5 6 7 2 1
public class ArraySpiralPrinter { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); //marrix size //read array int[][] ar = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { ar[i][j] = sc.nextInt(); } } printTopRight(0, 0, n - 1, n - 1, ar); } //prints top and right layers. //(x1,y1) to (x1, y2) - top layer & (x1,y2) to (x2, y2) private static void printTopRight(int x1, int y1, int x2, int y2, int[][] ar) { //print row values - top for (int y = y1; y <= y2; y++) { System.out.printf("%d ", ar[x1][y]); } //print column value - right for (int x = x1 + 1; x <= x2; x++) { System.out.printf("%d ", ar[x][y2]); } //are there any remaining layers if (x2 - x1 > 0) { //call printBottemLeft printBottomLeft(x1 + 1, y1, x2, y2 - 1, ar); } } //prints bottom and left layers in reverse order //(x2,y2) to (x2, y1) - bottom layer & (x2,y1) to (x1, y1) private static void printBottomLeft(int x1, int y1, int x2, int y2, int[][] ar) { //print row values in reverse order - bottom for (int y = y2; y >= y1; y--) { System.out.printf("%d ", ar[x2][y]); } //print column value in reverse order - left for (int x = x2-1; x >= x1; x--) { System.out.printf("%d ", ar[x][y1]); } //are there any remaining layers if (x2 - x1 > 0) { printTopRight(x1, y1 + 1, x2 - 1, y2, ar); } } }
这是一个C的recursion版本，我可以想到： –
void printspiral (int[][100],int, int, int, int); int main() { int r,c, i, j; printf ("Enter the dimensions of the matrix"); scanf("%d %d", &r, &c); int arr[r][100]; int min = (r<c?r:c); if (min%2 != 0) min = min/2 +1; for (i = 0;i<r; i++) for (j = 0; j<c; j++) scanf ("%d",&arr[i][j]); printspiral(arr,0,r,c,min ); } void printspiral (int arr[][100], int i, int j, int k, int min) { int a; for (a = i; a<k;a++) printf("%d\n", arr[i][a]); for (a=i+1;a<j;a++) printf ("%d\n", arr[a][k-1]); for (a=k-2; a>i-1;a--) printf("%d\n", arr[j-1][a]); for (a=j-2; a>i; a--) printf("%d\n", arr[a][i]); if (i < min) printspiral(arr,i+1, j-1,k-1, min); }
http://www.technicalinterviewquestions.net/2009/03/print-2d-array-matrix-spiral-order.html
这里是上面的答案的最好的解释:)随着图:)
public static void printSpiral1(int array[][],int row,int col){ int rowStart=0,colStart=0,rowEnd=row-1,colEnd=col-1; int i; while(rowStart<=rowEnd && colStart<= colEnd){ for(i=colStart;i<=colEnd;i++) System.out.print(" "+array[rowStart][i]); for(i=rowStart+1;i<=rowEnd;i++) System.out.print(" "+array[i][colEnd]); for(i=colEnd-1;i>=colStart;i--) System.out.print(" "+array[rowEnd][i]); for(i=rowEnd-1;i>=rowStart+1;i--) System.out.print(" "+array[i][colStart]); rowStart++; colStart++; rowEnd--; colEnd--; } }
public class SpiralPrint{ //print the elements of matrix in the spiral order. //my idea is to use recursive, for each outer loop public static void printSpiral(int[][] mat, int layer){ int up = layer; int buttom = mat.length - layer - 1; int left = layer; int right = mat[0].length - layer - 1; if(up > buttom+1 || left > right + 1) return; // termination condition //traverse the other frame, //print up for(int i = left; i <= right; i ++){ System.out.print( mat[up][i]+ " " ); } //print right for(int i = up + 1; i <=buttom; i ++){ System.out.print(mat[i][right] + " "); } //print buttom for(int i = right - 1; i >= left; i --){ System.out.print(mat[buttom][i] + " "); } //print left for(int i = buttom - 1; i > up; i --){ System.out.print(mat[i][left] + " "); } //recursive call for the next level printSpiral(mat, layer + 1); } public static void main(String[] args){ int[][] mat = {{1,2,3,4}, {5,6,7,8}, {9,10,11,12}, {13,14,15,16}}; int[][] mat2 = {{1,2,3}, {4,5,6}, {7,8,9}, {10,11,12}}; SpiralPrint.printSpiral(mat2,0); return; } }
这是我在C＃中的解决scheme：
public static void PrintSpiral(int[][] matrix, int n) { if (matrix == null) { return; } for (int layer = 0; layer < Math.Ceiling(n / 2.0); layer++) { var start = layer; var end = n - layer - 1; var offset = end - 1; Console.Write("Layer " + layer + ": "); // Center case if (start == end) { Console.Write(matrix[start][start]); } // Top for (int i = start; i <= offset; i++) { Console.Write(matrix[start][i] + " "); } // Right for (int i = start; i <= offset; i++) { Console.Write(matrix[i][end] + " "); } // Bottom for (int i = end; i > start; i--) { Console.Write(matrix[end][i] + " "); } // Left for (int i = end; i > start; i--) { Console.Write(matrix[i][start] + " "); } Console.WriteLine(); } }
这是我使用迭代器的方法。 注意这解决了几乎相同的问题。完整的代码在这里： https : //github.com/rdsr/algorithms/blob/master/src/jvm/misc/FillMatrix.java
import java.util.Iterator; class Pair { final int i; final int j; Pair(int i, int j) { this.i = i; this.j = j; } @Override public String toString() { return "Pair [i=" + i + ", j=" + j + "]"; } } enum Direction { N, E, S, W; } class SpiralIterator implements Iterator<Pair> { private final int r, c; int ri, ci; int cnt; Direction d; // current direction int level; // spiral level; public SpiralIterator(int r, int c) { this.r = r; this.c = c; d = Direction.E; level = 1; } @Override public boolean hasNext() { return cnt < r * c; } @Override public Pair next() { final Pair p = new Pair(ri, ci); switch (d) { case E: if (ci == c - level) { ri += 1; d = changeDirection(d); } else { ci += 1; } break; case S: if (ri == r - level) { ci -= 1; d = changeDirection(d); } else { ri += 1; } break; case W: if (ci == level - 1) { ri -= 1; d = changeDirection(d); } else { ci -= 1; } break; case N: if (ri == level) { ci += 1; level += 1; d = changeDirection(d); } else { ri -= 1; } break; } cnt += 1; return p; } private static Direction changeDirection(Direction d) { switch (d) { case E: return Direction.S; case S: return Direction.W; case W: return Direction.N; case N: return Direction.E; default: throw new IllegalStateException(); } } @Override public void remove() { throw new UnsupportedOperationException(); } } public class FillMatrix { static int[][] fill(int r, int c) { final int[][] m = new int[r][c]; int i = 1; final Iterator<Pair> iter = new SpiralIterator(r, c); while (iter.hasNext()) { final Pair p = iter.next(); m[pi][pj] = i; i += 1; } return m; } public static void main(String[] args) { final int r = 19, c = 19; final int[][] m = FillMatrix.fill(r, c); for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { System.out.print(m[i][j] + " "); } System.out.println(); } } }
用给定的行x列为任何二维数组matrix完成纯C程序。
#include <stdio.h> void printspiral(int *p,int r, int c) { int i=0,j=0,m=1,n=0; static int firstrun=1,gCol; if (!p||r<=0||c<=0) return ; if(firstrun) { gCol=c; firstrun=0; } for(i=0,j=0;(0<=i && i<c)&&(0<=j && j<r);i+=m,j+=n) { printf(" %d",p[i+j*gCol]); if (i==0 && j==1 && (i+1)!=c) break; else if (i+1==c && !j) {m=0;n=1;} else if (i+1==c && j+1==r && j) {n=0;m=-1;} else if (i==0 && j+1==r && j) {m=0;n=-1;} } printspiral(&p[i+j*gCol+1],r-2,c-2); firstrun=1; printf("\n"); } int main() { int a[3][3]={{0,1,2},{3,4,5},{6,7,8}}; int b[3][4]={{0,1,2,3},{4,5,6,7},{8,9,10,11}}; int c[4][3]={{0,1,2},{3,4,5},{6,7,8},{9,10,11}}; int d[3][1]={{0},{1},{2}}; int e[1][3]={{0,1,2}}; int f[1][1]={{0}}; int g[5][5]={{0,1,2,3,4},{5,6,7,8,9},{10,11,12,13,14},{15,16,17,18,19},{20,21,22,23,24}}; printspiral(a,3,3); printspiral(b,3,4); printspiral(c,4,3); printspiral(d,3,1); printspiral(e,1,3); printspiral(f,1,1); printspiral(g,5,5); return 0; }
这个问题与这个有关：在matrix安排问题在PHP
所提出的答案似乎有效，但却很难理解。 解决这个问题的一个非常简单的方法就是分而治之，也就是说，在阅读边缘之后，将其删除，下一个阅读将会简单得多。 在下面的PHP中查看一个完整的解决scheme：
#The source number matrix $source[0] = array(1, 2, 3, 4); $source[1] = array(5, 6, 7, 8); $source[2] = array(9, 10, 11, 12); $source[3] = array(13, 14, 15, 16); $source[4] = array(17, 18, 19, 20); #Get the spiralled numbers $final_spiral_list = get_spiral_form($source); print_r($final_spiral_list); function get_spiral_form($matrix) { #Array to hold the final number list $spiralList = array(); $result = $matrix; while(count($result) > 0) { $resultsFromRead = get_next_number_circle($result, $spiralList); $result = $resultsFromRead['new_source']; $spiralList = $resultsFromRead['read_list']; } return $spiralList; } function get_next_number_circle($matrix, $read) { $unreadMatrix = $matrix; $rowNumber = count($matrix); $colNumber = count($matrix[0]); #Check if the array has one row or column if($rowNumber == 1) $read = array_merge($read, $matrix[0]); if($colNumber == 1) for($i=0; $i<$rowNumber; $i++) array_push($read, $matrix[$i][0]); #Check if array has 2 rows or columns if($rowNumber == 2 || ($rowNumber == 2 && $colNumber == 2)) { $read = array_merge($read, $matrix[0], array_reverse($matrix[1])); } if($colNumber == 2 && $rowNumber != 2) { #First read left to right for the first row $read = array_merge($read, $matrix[0]); #Then read down on right column for($i=1; $i<$rowNumber; $i++) array_push($read, $matrix[$i][1]); #..and up on left column for($i=($rowNumber-1); $i>0; $i--) array_push($read, $matrix[$i][0]); } #If more than 2 rows or columns, pick up all the edge values by spiraling around the matrix if($rowNumber > 2 && $colNumber > 2) { #Move left to right for($i=0; $i<$colNumber; $i++) array_push($read, $matrix[0][$i]); #Move top to bottom for($i=1; $i<$rowNumber; $i++) array_push($read, $matrix[$i][$colNumber-1]); #Move right to left for($i=($colNumber-2); $i>-1; $i--) array_push($read, $matrix[$rowNumber-1][$i]); #Move bottom to top for($i=($rowNumber-2); $i>0; $i--) array_push($read, $matrix[$i][0]); } #Now remove these edge read values to create a new reduced matrix for the next read $unreadMatrix = remove_top_row($unreadMatrix); $unreadMatrix = remove_right_column($unreadMatrix); $unreadMatrix = remove_bottom_row($unreadMatrix); $unreadMatrix = remove_left_column($unreadMatrix); return array('new_source'=>$unreadMatrix, 'read_list'=>$read); } function remove_top_row($matrix) { $removedRow = array_shift($matrix); return $matrix; } function remove_right_column($matrix) { $neededCols = count($matrix[0]) - 1; $finalMatrix = array(); for($i=0; $i<count($matrix); $i++) $finalMatrix[$i] = array_slice($matrix[$i], 0, $neededCols); return $finalMatrix; } function remove_bottom_row($matrix) { unset($matrix[count($matrix)-1]); return $matrix; } function remove_left_column($matrix) { $neededCols = count($matrix[0]) - 1; $finalMatrix = array(); for($i=0; $i<count($matrix); $i++) $finalMatrix[$i] = array_slice($matrix[$i], 1, $neededCols); return $finalMatrix; }
// Program to print a matrix in spiral order #include <stdio.h> int main(void) { // your code goes here int m,n,i,j,k=1,c1,c2,r1,r2;; scanf("%d %d",&m,&n); int a[m][n]; for(i=0;i<m;i++) { for(j=0;j<n;j++) { scanf("%d",&a[i][j]); } } r1=0; r2=m-1; c1=0; c2=n-1; while(k<=m*n) { for(i=c1;i<=c2;i++) { k++; printf("%d ",a[r1][i]); } for(j=r1+1;j<=r2;j++) { k++; printf("%d ",a[j][c2]); } for(i=c2-1;i>=c1;i--) { k++; printf("%d ",a[r2][i]); } for(j=r2-1;j>=r1+1;j--) { k++; printf("%d ",a[j][c1]); } c1++; c2--; r1++; r2--; } return 0; }
This is java implementation for any mxn matrix. Where rows = No. of rows and Column = No. of Columns
public static void printSpiral(int rows, int columns, int a[][]) { int i, k = 0, l = 0; /* k - starting row index l - starting column index */ while (k < rows && l < columns) { /* Print the first row from the remaining rows */ for (i = l; i < columns; ++i) { System.out.println(a[k][i]); } k++; /* Print the last column from the remaining columns */ for (i = k; i < rows; ++i) { System.out.println(a[i][columns-1]); } columns--; /* Print the last row from the remaining rows */ if ( k < rows) { for (i = columns-1; i >= l; --i) { System.out.println(a[rows-1][i]); } rows--; } /* Print the first column from the remaining columns */ if (l < columns) { for (i = rows-1; i >= k; --i) { System.out.println(a[i][l]); } l++; } } }
Just keep it simple –>
public class spiralMatrix { public static void printMatrix(int[][] matrix, int rows, int col) { int rowStart=0; int rowEnd=rows-1; int colStart=0; int colEnd=col-1; while(colStart<=colEnd && rowStart<=rowEnd) { for(int i=colStart;i<colEnd;i++) System.out.println(matrix[rowStart][i]); for(int i=rowStart;i<rowEnd;i++) System.out.println(matrix[i][colEnd]); for(int i=colEnd;i>colStart;i--) System.out.println(matrix[rowEnd][i]); for(int i=rowEnd;i>rowStart;i--) System.out.println(matrix[i][colStart]); rowStart++; colEnd--; rowEnd--; colStart++; } } public static void main(String[] args){ int[][] array={{1,2,3,4},{5,6,7,8}}; printMatrix(array,2,4); }
}
这是我的解决scheme。 Please correct if I'm wrong.
class Spiral: def spiralOrder(self, A): result = [] c = [] c.append(A[0]) b = A[1:] while len(b) > 0: b = self.rotate(b) c.append(b[0]) b = b[1:] for item in c: for fitem in item: print fitem, result.append(fitem) return result def rotate(self,a): b = [] l = zip(*a) for i in xrange(len(l)-1,-1,-1): b.append(list(l[i])) return b if __name__ == '__main__': a = [[1, 2, 3,3], [4, 5, 6,6], [7, 8, 9,10]] s = Spiral() s.spiralOrder(a)
