螺旋矩陣算法問題

    螺旋矩陣算法問題，大緻描述如下，給出一個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的矩陣資料：

    列印的軌迹類似螺旋，是以也叫螺旋矩陣。

    這個題目還有一個變種，就是生成一個矩陣，矩陣的資料按照螺旋式結構填充。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)。