This is the 21st day of my participation in the August Text Challenge.More challenges in August

preface

The spiral matrix of question 54 is as follows:

You are given a matrix matrix with m rows and n columns. Please return all elements in the matrix in clockwise spiral order.

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

A, thinking

There is one important piece of information in the spiral matrix:

  • The order of traversal is:-,left,please,write

So now that we know the order of the traversal, we need to know how many cycles are there in this matrix with m rows and n columns?

So a 3 x 4 matrix has 2 cycles

A 4 by 4 matrix also has 2 circles

From the above we can conclude that the winding number of the m x n matrix is: if the smaller side length is even, then the winding number is divided by 2. If the length of the smaller side is even, the winding number is divided by 2 and then added by 1

Through the above two steps, we know the number of loops to be traversed and the order of traversal, so the steps can be roughly divided into the following two steps:

  1. From outside to inside, according to the number of turns
  2. In the current circle-,left,please,writeSequential traversal of

For example

Here in matrix in the sample 2 = [[1, 2, 3, 4], [5,6,7,8], [9,10,11,12]] as an example, the matrix is shown below:

  1. Traverse the outer circle 1, from left to right. You can get elements{1, 2, 3, 4}

  1. Go through the outer circle 1, top to bottom. You can get elements12} {8.(Note that the starting point here isi+1Can no longer get4A)

  1. Traverse outer circle 1, from right to left. You can get elements{11, 10, 9}(Note that the starting point here is(m-1)-iCan no longer get12A)

  1. Go through the outer circle 1, from bottom to top. You can get elements{5}(Note that the bottom is no longer available here9And at the top of the1A)

  1. Traverse the outer circle 2, from left to right. You can get elements{6, 7}

  1. Finally, the result is returned{1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7}Can be

Second, the implementation

The implementation code

The implementation code is consistent with the idea

    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ret = new ArrayList<>();  / / the result set
        if(matrix == null || matrix.length == 0)
            return ret;
        int m = matrix.length;  / / line
        int n = matrix[0].length;   / / column
        int i = 0;
        int minLen = Math.min(m, n);
        // How many circles are there (one more circle if the number is odd)
        int count = minLen % 2 > 0 ?  minLen/ 2 + 1 : minLen/2;
        // Layer by layer from the outside to the inside
        while(i < count) {
            / / to the left
            for (int j = i; j < n-i; j++) {
                ret.add(matrix[i][j]);
            }
            / / down
            for (int j = i+1; j < m-i; j++) {
                ret.add(matrix[j][(n-1)-i]);
            }
            / / to the left
            for (int j = (n-1)-(i+1); j >= i && (m-1-i ! = i); j--) { ret.add(matrix[(m-1)-i][j]);
            }
            / / up
            for (int j = (m-1)-(i+1); j >= i+1 && (n-1-i) ! = i; j--) { ret.add(matrix[j][i]); } i++; }return ret;
    }
Copy the code

The test code

    public static void main(String[] args) {
        int[][] matrix = {{1.2.3.4}, {5.6.7.8}, {9.10.11.12}};
        new Number54().spiralOrder(matrix);
    }
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥