Day32 螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素

https://leetcode-cn.com/problems/spiral-matrix/

示例1：

image

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例2：

image

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

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100

Java解法

思路：

• 顺时针输出，由外向内，起点都是左上角
• 考虑记录圈数，记录每圈输出规则
  • 这里要注意当圈为一横 或一竖的情况（需要计算好边界，注意重复与遗漏）

package sj.shimmer.algorithm.m2;

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

/**
 * Created by SJ on 2021/2/25.
 */

class D32 {
    public static void main(String[] args) {
        System.out.println(spiralOrder(new int[][]{{2},{3}}));
        System.out.println(spiralOrder(new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9},}));
        System.out.println(spiralOrder(new int[][]{{1,2,3,4},{5,6,7,8},{9,10,11,12}}));
    }

    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        if (matrix != null) {
            int height = matrix.length;
            int width = matrix[0].length;
            int maxTurn = (Math.min(height, width)+1) / 2;
            for (int i = 0; i < maxTurn; i++) {
                int top = i;
                while (top < width - i) {
                    list.add(matrix[i][top]);
                    top++;
                }
                int right = i+1;
                while (right < height - i-1) {
                    list.add(matrix[right][width-i-1]);
                    right++;
                }
                if (i==height-1-i) {
                    continue;
                }
                int bottom = width-i-1;
                while (bottom >= i) {
                    list.add(matrix[height-i-1][bottom]);
                    bottom--;
                }
                if (i==width-i-1) {
                    continue;
                }
                int left = height-i-2;
                while (left > i) {
                    list.add(matrix[left][i]);
                    left--;
                }
            }
        }
        return list;
    }
}

image

官方解

https://leetcode-cn.com/problems/spiral-matrix/solution/luo-xuan-ju-zhen-by-leetcode-solution/

1. 模拟

   使用辅助矩阵来模拟路径，不是特别有想法的解法

   • 时间复杂度：O(mn)
   • 空间复杂度：O(mn)

2. 按层模拟

   差不多的思路，但解法有一些区别

   class Solution {
       public List<Integer> spiralOrder(int[][] matrix) {
           List<Integer> order = new ArrayList<Integer>();
           if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
               return order;
           }
           int rows = matrix.length, columns = matrix[0].length;
           int left = 0, right = columns - 1, top = 0, bottom = rows - 1;
           while (left <= right && top <= bottom) {
               for (int column = left; column <= right; column++) {
                   order.add(matrix[top][column]);
               }
               for (int row = top + 1; row <= bottom; row++) {
                   order.add(matrix[row][right]);
               }
               if (left < right && top < bottom) {
                   for (int column = right - 1; column > left; column--) {
                       order.add(matrix[bottom][column]);
                   }
                   for (int row = bottom; row > top; row--) {
                       order.add(matrix[row][left]);
                   }
               }
               left++;
               right--;
               top++;
               bottom--;
           }
           return order;
       }
   }
   

   • 时间复杂度：O(mn)
   • 空间复杂度：O(1)