Title address

54. Spiral matrix

Topic describes

Print the matrix clockwise

The official answer key

The main idea is simulation

Method 1: simulation

Can simulate the path of spiral matrix. The initial position is the upper left corner of the matrix, the initial direction is to the right, and when the path goes out of bounds or into a previously visited position, it rotates clockwise to the next direction.

An auxiliary matrix visited\ Textit {visited}visited with the same size as the input matrix is used to determine whether the path has entered the previously visited location, where each element indicates whether the location has been visited. When an element is visited, set the element at the corresponding position in visited\ Textit {visited}visited as visited.

How do I determine whether a path ends? Since every element in the matrix is accessed once, the length of the path is the number of elements in the matrix. When the length of the path reaches the number of elements in the matrix, it is the complete path and the path is returned.

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;
        boolean[][] visited = new boolean[rows][columns];
        int total = rows * columns;
        int row = 0, column = 0;
        int[][] directions = {{0.1}, {1.0}, {0, -1}, {-1.0}};
        int directionIndex = 0;
        for (int i = 0; i < total; i++) {
            order.add(matrix[row][column]);
            visited[row][column] = true;
            int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
            if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {
                directionIndex = (directionIndex + 1) % 4;
            }
            row += directions[directionIndex][0];
            column += directions[directionIndex][1];
        }
        returnorder; }}Copy the code

Complexity analysis

  • Time complexity: O(Mn), where M and n are the number of rows and columns of the input matrix respectively. Each element in the matrix is accessed once.

  • Space complexity: O(MN). It is necessary to create a matrix of size M ×nm × times nm×n visited textit{visited}visited to record whether each location has been visited.

Method two: layer simulation

You can think of a matrix as a number of layers, first printing the outermost element, then the next outermost element, until the innermost element.

The KTH layer of the definition matrix is all vertices k away from the nearest boundary. For example, in the matrix below, the outermost elements are layer 1, the next outermost elements are layer 2, and the remaining elements are layer 3.

For each layer, all elements are traversed clockwise from the top left. Assuming the top left corner of the current layer is located at (top,left)(\ Textit {top}, \ Textit {left})(top,left), The lower right corner is located at (bottom,right)(\ Textit {bottom}, \ Textit {right})(bottom,right), traversing the elements of the current layer in the following order.

Traverse the top elements from left to right, in order: (top,left)(\textit{top}, \ Textit {left})(top,left) to (top,right)(\ Textit {top}, \textit{right})(top,right).

I’m going to go from top to bottom, \textit{top} +1, \ Textit {right})(top+1, \textit{right})(top+1,right) to (bottom,right)(\textit{bottom}, \ textit} {right) (bottom right).

If left

After iterating through the elements of the current layer, increment left\textit{left}left and top\textit{top}top respectively by 1, Reduce right\textit{right}right and bottom\textit{bottom}bottom by 1, respectively, and proceed to the next level to continue traversing until all elements are traversed.

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--;
        }
        returnorder; }}Copy the code

Complexity analysis

  • Time complexity: O(Mn), where M and n are the number of rows and columns of the input matrix respectively. Each element in the matrix is accessed once.
  • Space complexity: O(1). Except for the output array, the space complexity is constant.

His writing

More ugly

class Solution { public List<Integer> spiralOrder(int[][] matrix) { int minRow = 0; int maxRow = matrix.length - 1; int minColumn = 0; int maxColumn = matrix[0].length - 1; int i = 0; int j = 0; List<Integer> result = new ArrayList<>(matrix.length * matrix[0].length); while (minRow <= i && maxRow >= i && minColumn <= j && maxColumn >= j) { while (minRow <= i && maxRow >= i && minColumn <= j && maxColumn >= j) { result.add(matrix[i][j++]); } minRow++; i++; j--; while(minRow <= i && maxRow >= i && minColumn <= j && maxColumn >= j) { result.add(matrix[i++][j]); } maxColumn--; i--; j--; while (minRow <= i && maxRow >= i && minColumn <= j && maxColumn >= j) { result.add(matrix[i][j--]); } maxRow--; i--; j++; while(minRow <= i && maxRow >= i && minColumn <= j && maxColumn >= j) { result.add(matrix[i--][j]); } minColumn++; i++; j++; } return result; }}Copy the code