54. 螺旋矩阵

题目描述:

给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。

示例 1:

输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
示例 2:

输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

解法1:

新创建一个与矩阵同大小的Boolean矩阵,将已经走过的位置置true,然后拐弯的时候判断一下是不是已经走过了或者是不是超过边界,如果走过了(根据boolean矩阵值是否为空)或超出边界就计算一下新的方向:

package array;

import java.util.ArrayList;
import java.util.List;

public class L54_2 {
    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        //下方用到matrix[0],所以需要防止出现空值情况
        if(matrix.length == 0){return list;}
        //用于指示下一个数据的位置
        int[] dx ={0, 1, 0, -1},dy = {1, 0, -1, 0};
        int station_x = 0, station_y = 0 , station_xnew = 0, station_ynew = 0,
        dirt_xy = 0,index = 0;
        Boolean[][] matrix_boolean = new Boolean[matrix.length][matrix[0].length];
        //遍历矩阵所有数据的长度
        while(index < matrix.length*matrix[0].length){
            list.add(matrix[station_x][station_y]);
            matrix_boolean[station_x][station_y] = true;
            //station_xnew,station_ynew用于验证该位置的数据合法性
            station_xnew = station_x + dx[dirt_xy];station_ynew = station_y + dy[dirt_xy];
            if( station_xnew >=0 &&  station_xnew <= matrix.length-1 && station_ynew >=0 &&  station_ynew <=matrix[0].length-1
                    && (matrix_boolean[station_xnew][station_ynew] == null)){
                matrix_boolean[station_xnew][station_ynew] = false;
                station_x = station_xnew;station_y = station_ynew;
            }else{
                dirt_xy = (++ dirt_xy) % 4;
                station_x += dx[dirt_xy];station_y += dy[dirt_xy];
            }
            index ++;
        }
        return list;
    }
    public static void main(String[] args) {
        int[][] matrix = {{1,2,3},{4,5,6},{7,8,9}};
        List<Integer> ll = spiralOrder(matrix);
        for (int i =0;i<ll.size();i++){
            System.out.println(ll.get(i));
        }
    }
}

解法2:

相比于上一个方法更好理解,主要就是从外圈逐渐向里圈逐渐遍历

package array;

import java.util.ArrayList;
import java.util.List;

public class L54 {
    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        if(matrix.length == 0){return list;}
        //遍历的圈数,是长与宽之间最小值决定的
        int cir_Time = Math.min(matrix.length,matrix[0].length);
        int start = 0;
        while(start <= (cir_Time-1)/2){
            for(int index = start;index <= matrix[0].length-1-start;index++) list.add(matrix[start][index]);

            for(int index = start+ 1;index < matrix.length-1-start;index++)  list.add(matrix[index][matrix[0].length-1-start]);

            if(start != matrix.length-1-start){
                for(int index = matrix[0].length-1-start;index >= start;index--) list.add(matrix[matrix.length-1-start][index]);
            }
            if(start != matrix[0].length-1-start){
                for(int index = matrix.length-start-2;index > start;index--) list.add(matrix[index][start]);
            }
            start++;
        }
        return list;
    }
    public static void main(String[] args) {
        int[][] matrix = {{1,2},{3,4}};
        List<Integer> ll = spiralOrder(matrix);
        for (int i =0;i<ll.size();i++){
            System.out.println(ll.get(i));
        }
    }
}

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。