“This is the 19th day of my participation in the August Gwen Challenge.

Topic describes

Enter a matrix and print out each number in clockwise order from the outside in.

Example 1:

Input: matrix = [[1, 2, 3], [4 and 6], [7,8,9]] output:,2,3,6,9,8,7,4,5 [1]Copy the code

Example 2:

Input: matrix = [[1, 2, 3, 4], [5,6,7,8], [9,10,11,12]] output:,2,3,4,8,12,11,10,9,5,6,7 [1]Copy the code

Limitations:

0 <= matrix.length <= 100

0 <= matrix[i].length <= 100

Copy the code

Answer key

Method 1: simulation, set boundaries

Their thinking

According to the example matrix = [[1,2,3],[4,5,6],[7,8,9]], it can be found that the order of clockwise printing matrix is “from left to right, from top to bottom, from right to left, from bottom to top”.

• Therefore, consider setting the matrix “left, up, right, down” four convenient, simulate the above matrix traversal sequence.

Algorithm flow:

1. Null value processing: When matrix is empty, simply return the empty list [].

2. Initialization: the matrix left, right, upper and lower four boundaries L, R, T, b, used to print the result list res.

3. Circular printing: “from left to right, from top to bottom, from right to left, from bottom to top” four directions of circulation, each direction of printing to do the following three things (see the following table for specific information in each direction) :

4. Print by border, adding elements sequentially to the end of the list RES;

5. The boundary shrinks inward by 1 (indicates that it has been printed);

6. Judge whether the printing is finished (whether the boundaries meet), if the printing is finished, jump out.

7. Return value: Return res.

The print direction	1. Print according to boundaries	2. Boundaries shrink inward	3. Check whether the printing is complete
From left to right	Left bound L, right bound R	The upper boundary is t plus 11	Is t greater than B
From the top down	Upper bound t, lower bound B	The right boundary r minus 11	Whether l > r
From right to left	R on the right, l on the left	The lower boundary b minus 11	Is t greater than B
From the bottom up	Lower boundary B, upper boundary T	The left boundary l plus 11	Whether l > r

Complexity analysis:

Time complexity O(MN) : M and N are the number of rows and columns of the matrix respectively.

Space complexity O(1) : Four boundaries L, R, T, b use extra space of constant size (res is the space that must be used).

code

Java code takes advantage of the convenience of ++ operations

• res[x++]This is equivalent to giving firstres[x]Assign and givexSince the increase 1;

• ++t > bThis is equivalent to giving firsttIncrement by 1t > bLogical expression.

class Solution {

    public int[] spiralOrder(int[][] matrix) {

        if(matrix.length == 0) return new int[0];

        int l = 0, r = matrix[0].length - 1, t = 0, b = matrix.length - 1, x = 0;

        int[] res = new int[(r + 1) * (b + 1)];

        while(true) {

            for(int i = l; i <= r; i++) res[x++] = matrix[t][i]; // left to right.

            if(++t > b) break;

            for(int i = t; i <= b; i++) res[x++] = matrix[i][r]; // top to bottom.

            if(l > --r) break;

            for(int i = r; i >= l; i--) res[x++] = matrix[b][i]; // right to left.

            if(t > --b) break;

            for(int i = b; i >= t; i--) res[x++] = matrix[i][l]; // bottom to top.

            if(++l > r) break;

        }

    returnres; }}Copy the code

Personal understanding

1. Rule: There is a rule, the method is clockwise to print the corresponding is a cycle, the cycle is from left to right, from top to bottom, from right to left, from bottom to top, through the loop can solve the problem of direction, we don’t have to control the direction of how to change, we only need a while loop, in the case of a condition is met, executed in sequence the traversal in all directions, It’s directional control.

2. Left =0, right= matrix.length, top=0, bottom=matrix.length

3. We need to define an array that returns the result[], and we need to define an index index that we can use to write data to the array, that is, index=0.

4. Loop assignment: How do we loop assignment? For example, from left to right, we need to find the left boundary and the right boundary, left and right, and iterate from left to right. So how do we determine which value in the array? We also need to know which row we are in, so we need the top parameter, and we know from matrix[top][I] which value is in the data.

5. What boundaries to judge: How and what boundaries should we judge when we are done iterating in one direction? Taking left to right for example, after that direction is traversed, our next direction should be top to bottom, so we should determine whether the top to bottom boundary has been crossed.

6. How to compare boundaries: For example, from left to right, we should compare the upper and lower boundaries. So what is beyond the boundary? Top =bottom means it should be the last row traversed, so top>bottom is out of bounds.

7. Top, bottom is the horizontal coordinate, left, right is the vertical coordinate.

The following code is written according to my own understanding, which is the above code after simplification:

class Solution { public int[] spiralOrder(int[][] matrix) { if (matrix.length == 0 || matrix[0].length == 0) { return new int[0]; } int left = 0; int right = matrix[0].length - 1; int top = 0; int bottom = matrix.length - 1; int length = matrix.length*matrix[0].length; int[] result = new int[length]; int index = 0; While (true) {// for (int I =left; i<=right; i++) { result[index] = matrix[top][i]; index++; } top++; if (top > bottom) { break; } // for (int I =top; i<=bottom; i++) { result[index] = matrix[i][right]; index++; } right--; if(left > right) { break; } // for (int I =right; i>=left; i--) { result[index] = matrix[bottom][i]; index++; } bottom--; if(top > bottom) { break; } // for(int I =bottom; i>=top; i--) { result[index] = matrix[i][left]; index++; } left++; if (left > right) { break; } } return result; }}Copy the code

source

Author: jyd

Link: leetcode-cn.com/problems/sh…

Source: LeetCode