螺旋矩阵算法问题

迈不过友情╰ 2022-10-20 13:50 128阅读 0赞

螺旋矩阵算法问题，大致描述如下，给出一个n\*n的矩阵，螺旋式打印，比如：  
    \[\[ 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,12,9,5,6,7,11,10。

如下图所示，依次获取4\*4的矩阵数据：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70][]

打印的轨迹类似螺旋，因此也叫螺旋矩阵。

这个题目还有一个变种，就是生成一个矩阵，矩阵的数据按照螺旋式结构填充。4\*4的矩阵就变为了：

\[\[ 1, 2, 3, 4\],  
     \[12,13,14, 5\],  
     \[11,16,15, 6\],  
     \[10, 9, 8, 7\]\]

这个题目，结果很直观，解决思路就是需要判断各种临界条件，可以考虑按照四个方向：从左到右，从上到下，从右到左，从下到上的顺序遍历或者循环，然后将对应的数据获取或者填入对应的位置。

package com.xxx.huali.hualitest.algorithm;
    import java.util.ArrayList;
    import java.util.List;
    public class SpiralMatrix {
    	
    	/**
    	 * 螺旋式排列
    	 * @param data
    	 * @return
    	 */
    	public static List<Integer> spiralOrder(int[][] data){
    		List<Integer> list = new ArrayList<Integer>();
    		if(data==null)
    			return null;
    		int size = data.length;
    		int beginX = 0,endX = size-1;
    		int beginY = 0,endY = size-1;
    		while(true) {
    			for(int j=beginX;j<=endX;++j)list.add(data[beginX][j]);
    			if(++beginY>endY)break;
    			for(int i=beginY;i<=endY;++i)list.add(data[i][endX]);
    			if(beginX>--endX)break;
    			for(int j=endX;j>=beginX;--j)list.add(data[endY][j]);
    			if(beginY>--endY)break;
    			for(int i=endY;i>=beginY;--i)list.add(data[i][beginX]);
    			if(++beginX>endX)break;
    		}
    		return list;
    	}
    	
    	/**
    	 * 构建螺旋式矩阵
    	 * @param n
    	 * @return
    	 */
    	public static int[][] getMatrix(int n){
    		int [][] data = new int[n][n];
    		if(n==0)return null;
    		int beginX = 0,endX = n-1;
    		int beginY = 0,endY = n-1;
    		int num = 1;
    		while(true) {
    			for(int j=beginX;j<=endX;++j)data[beginX][j] = num++;
    			if(++beginY>endY)break;
    			for(int i=beginY;i<=endY;++i)data[i][endX] = num++;
    			if(beginX>--endX)break;
    			for(int j=endX;j>=beginX;--j)data[endY][j] = num++;
    			if(beginY>--endY)break;
    			for(int i=endY;i>=beginY;--i)data[i][beginX] = num++;
    			if(++beginX>endX)break;
    		}
    		return data;
    	}
    	
    	public static void main(String[] args) {
    		int [][] data = new int[][] {
       {1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
    		List<Integer> list = spiralOrder(data);
    		for(Integer d:list) {
    			System.out.print(d+" ");
    		}
    		System.out.println();
    		System.out.println("======================================");
    		int[][] data2 = getMatrix(4);
    		for(int i=0;i<data2.length;i++) {
    			for(int j=0;j<data2.length;j++) {
    				System.out.print(data2[i][j]+"\t");
    			}
    			System.out.println();
    		}
    	}
    }

运行程序，打印结果：

1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 
    ======================================
    1	2	3	4	
    12	13	14	5	
    11	16	15	6	
    10	9	8	7

算法时间复杂度都是O(n^2)。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70]: /images/20221020/3f03d7dd7a154e67b0c65c4b3c55a850.png