给定一个m x n大小的矩阵(m行,n列),按螺旋的顺序返回矩阵中的所有元素。

文章目录

题目:

给定一个m x n大小的矩阵(m行,n列),按螺旋的顺序返回矩阵中的所有元素。
例如:输入[[1,2,3],[4,5,6],[7,8,9]]
返回值[1,2,3,6,9,8,7,4,5]

解决:

1,找出螺旋的规律
分析:

1 2 3    返回螺旋 1 2 3 6 9 8 7 4 5
4 5 6
7 8 9 

2,边界的判断,到达矩阵的中心最小的圈时终止。由于行列不相等,因此定义四个变量用于记录边界:左边界left;右边界right;上边界top;下边界bottom。
然后以top和left基准层层打印,值得注意的是,为了避免重复打印,我们需要在打印下边和左边时额外判断一下top和bottom以及left和right是否相等:

 while( top < (matrix.length+1)/2 && left < (matrix[0].length+1)/2 ){
            //上面  左到右
            for(int i = left; i <= right; i++){
                res.add(matrix[top][i]);
            }

            //右边 上到下
            for(int i = top+1; i <= bottom; i++){
                res.add(matrix[i][right]);
            }

            //下面  右到左
            for(int i = right-1; top!=bottom && i>=left; i--){
                res.add(matrix[bottom][i]);
            }

            //左边 下到上
            for(int i = bottom-1; left!=right && i>=top+1; i--){
                res.add(matrix[i][left]);
            }
            ++top;
            --bottom;
            ++left;
            --right;
        }

完整代码加测试代码

package 牛客网算法刷题;
import java.util.*;

public class 螺旋矩阵 {
	
public static ArrayList<Integer> spiralOrder(int[][] matrix) {
    ArrayList<Integer> res = new ArrayList<>();
    if(matrix.length == 0)
        return res;
    int top = 0, bottom = matrix.length-1;
    int left = 0, right = matrix[0].length-1;

    while( top < (matrix.length+1)/2 && left < (matrix[0].length+1)/2 ){
        //上面  左到右
        for(int i = left; i <= right; i++){
            res.add(matrix[top][i]);
        }

        //右边 上到下
        for(int i = top+1; i <= bottom; i++){
            res.add(matrix[i][right]);
        }

        //下面  右到左
        for(int i = right-1; top!=bottom && i>=left; i--){
            res.add(matrix[bottom][i]);
        }

        //左边 下到上
        for(int i = bottom-1; left!=right && i>=top+1; i--){
            res.add(matrix[i][left]);
        }
        ++top;
        --bottom;
        ++left;
        --right;
    }
    return res;
    
    
}

public static void main(String[] args) {
    //请在此测试你写的方法
    //测试
    test();
}
private static void test() {
	// TODO Auto-generated method stub
	 int[][] matrix = {{1, 2, 3},{4, 5, 6},{7, 8, 9},{1, 2, 3}};
	 ArrayList<Integer> result = spiralOrder(matrix);
     System.out.println("你的输入为:"+Arrays.deepToString(matrix));
     System.out.print("你的输出为:");
     System.out.println(result);
     
     }

}

易错:二维数组输出是地址而非值

同理用其他语言:

C++

#include <vector>
using namespace std;

class 螺旋矩阵 {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        vector<int> res;
        if (matrix.empty()) return res;
        int top = 0, bottom = matrix.size() - 1;
        int left = 0, right = matrix[0].size() - 1;
        while (top < (matrix.size()+1) / 2 && left < (matrix[0].size()+1) / 2) {
            // 上
            for (int i = left; i <= right; ++i) {
                res.push_back(matrix[top][i]);
            }
            // 右
            for (int i = top + 1; i <= bottom; ++i) {
                res.push_back(matrix[i][right]);
            }
            // 下,注意这里的top!=bottom
            for (int i = right - 1; top != bottom && i >= left; --i) {
                res.push_back(matrix[bottom][i]);
            }
            // 左,注意这里的left!=right
            for (int i = bottom - 1; left != right && i >= top + 1; --i) {
                res.push_back(matrix[i][left]);
            }
            ++top, --bottom, ++left, --right;
        }
        return res;
    }
};

Python解法

class Solution:
    def spiralOrder(self , matrix ):
        res = []
        while matrix:
            res += matrix[0]
            matrix = list(zip(*matrix[1:]))[::-1]
        return res
上一篇:css自定义border


下一篇:画堆积柱形图