回旋矩阵算法题解题思路

原帖见：深圳一家公司面试问题,很囧

http://www.iteye.com/topic/545378

 

题目要求打印一个回旋数字矩阵

int i=5;
1  2  3  4  5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

int i=6
1  2  3  4  5   6
20 21 22 23 24  7
19 32 33 34 25  8
18 31 36 35 26  9
17 30 29 28 27 10
16 15 14 13 12 11

 

我的解题思路分析：

1.将此矩阵分解为一个一个的圈，如下图，1-20可以看成一个圈，21-32是一个圈，33-36也是一个圈。

 2.再将圈分解为四个均等的数列

 3.打印的过程中用一个二维数组存储矩阵，记录圈数 ，当前圈的数列长度 和圈开始计数的数字 。如i=6，第1圈时数列长为5，开始计数的数字为0；第2圈数列长为3，开始计数的数字为20；从这些规律总结出,已知变长为i，假设当前圈数为count，则数列长step=i-1-count*2

程序代码：

package snakematrix;

/**
 * @author Heis
 * @date Dec 11, 2009
 */
public class SnakeNum {

	
	public static void main(String[] args){
		int i=6;
		SnakeNum.print(SnakeNum.fill(i));		
	}
	/**
	 * 
	 * 算法复杂度为n
	 * 以下的算法，在for循环内的一些计算是不必要的，可以用变量保存，但是为了代码更加直观，就不做优化了。
	 * 
	 * @param i 矩阵边长
	 */
	public static int[][] fill(int i){
		Long startTime=System.currentTimeMillis();
		//第几圈
		int count=0;
		//数列长度
		int step;
		//总圈数
		int all;
		//某圈开始计数的基数
		int startNum=0;
		//用于数组下标计算
		int startIndex;
		int k;
		int[][] array=null;
		if(i>0){
			array=new int[i][i];
		    all=i/2+i%2;
		    while(all>=count){
		    	step=i-1-(count<<1);
		    	count++;
		    			    	
		    	for(startIndex=count-1,k=1;k<step+1;k++){
		    		array[count-1][startIndex++]=startNum+k;	
		    	}
		    	
		    	for(startIndex=count-1,k=1;k<step+1;k++){
		    		array[startIndex++][i-count]=startNum+k+step;
		    	}
		    	
		    	for(startIndex=i-count,k=1;k<step+1;k++){
		    		array[i-count][startIndex--]=startNum+k+2*step;
		    	}
		    	
		    	for(startIndex=i-count,k=1;k<step+1;k++){
		    		array[startIndex--][count-1]=startNum+k+3*step;
		    	}
		    	startNum=4*step+startNum;
		    	
		    }
		    //当矩阵边长为基数时，打印最后一个数字
		    if(i%2>0){
		    	int mid=all-1;
		    	array[mid][mid]=i*i;
		    }
		}
		Long timeUsed=System.currentTimeMillis()-startTime;
		System.out.println("总用时："+timeUsed+"ms");
		return array;		
	}
	
	/**
	 * 打印数组
	 * 
	 * @param array
	 */
	public static void print(int[][] array){
		if(array!=null){
			int n=array.length;
			int i=0,j;
			int count=Integer.valueOf(n*n).toString().length()+1;
			for(;i<n;i++){
				for(j=0;j<n;j++){
					System.out.printf("%"+count+"d",array[i][j]);
				}
				System.out.println();
			}
		}
	}
}

 优化后的代码：

package snakematrix;

/**
 * @author Heis
 *
 */
public class SnakeNum2 {

	public static void main(String[] args){
		int i=6;
		SnakeNum2.print(SnakeNum2.fill(i));		
	}
	/**
	 * 
	 * 算法复杂度为n
	 * @param i 矩阵边长
	 */
	public static int[][] fill(int i){
		Long startTime=System.currentTimeMillis();
		//第几圈
		int count=0;
		//转弯步数
		int step;
		//总圈数
		int all;
		//某圈开始累加的基数
		int startNum=0;
		//用于数组下标计算
		int startIndex;
		int k,cache=0;
		int[][] array=null;
		if(i>0){
			array=new int[i][i];
		    all=i/2+i%2;
		    while(all>=count){
		    	step=i-1-(count<<1);
		    	count++;
		    			    	
		    	for(startIndex=count-1,k=1;k<step+1;k++){
		    		array[count-1][startIndex++]=startNum+k;	
		    	}
		    	
		    	for(startIndex=count-1,k=1;k<step+1;k++){
		    		array[startIndex++][i-count]=startNum+k+step;
		    	}
		    	
		    	cache=(step<<1)+startNum;
		    	for(startIndex=i-count,k=1;k<step+1;k++){
		    		array[i-count][startIndex--]=cache+k;
		    	}
		    	
		    	cache=(step<<1)+startNum+step;
		    	for(startIndex=i-count,k=1;k<step+1;k++){
		    		array[startIndex--][count-1]=cache+k;
		    	}
		    	startNum=(step<<2)+startNum;		    	
		    }
		    //当矩阵边长为基数时，打印最后一个数字
		    if(i%2>0){
		    	int mid=all-1;
		    	array[mid][mid]=i*i;
		    }
		}
		Long timeUsed=System.currentTimeMillis()-startTime;
		System.out.println("总用时："+timeUsed+"ms");
		return array;		
	}
	
	/**
	 * 打印数组
	 * 
	 * @param array
	 */
	public static void print(int[][] array){
		if(array!=null){
			int n=array.length;
			int i=0,j;
			int count=Integer.valueOf(n*n).toString().length()+1;
			for(;i<n;i++){
				for(j=0;j<n;j++){
					System.out.printf("%"+count+"d",array[i][j]);
				}
				System.out.println();
			}
		}
	}
}

 

回帖还有另外一种思路，也是用一个二维数组存储数组，按照数列顺序输出，在输出过程中判断输出的方向，可以看这里的代码http://www.iteye.com/topic/545378?page=1#1288013

评论

1 楼 vinkeychen 2010-07-29  

向博主学习了。