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:
- From outside to inside, according to the number of turns
- In the current circle
-
,left
,please
,write
Sequential 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:
- Traverse the outer circle 1, from left to right. You can get elements
{1, 2, 3, 4}
- Go through the outer circle 1, top to bottom. You can get elements
12} {8.
(Note that the starting point here isi+1
Can no longer get4
A)
- Traverse outer circle 1, from right to left. You can get elements
{11, 10, 9}
(Note that the starting point here is(m-1)-i
Can no longer get12
A)
- Go through the outer circle 1, from bottom to top. You can get elements
{5}
(Note that the bottom is no longer available here9
And at the top of the1
A)
- Traverse the outer circle 2, from left to right. You can get elements
{6, 7}
- 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 ~♥