This is the 20th day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021.

describe

Given a matrix of m x n size (m rows, n columns), return all elements in the matrix in spiral order.

Data range: 0≤ n,m ≤10, all elements in the matrix satisfy ∣val∣≤100

Requirements: Space complexity O(nm), time complexity O(nm)

Example 1

Input:

[[1, 2, 3], [4 and 6], [7,8,9]]Copy the code

The return value:

,2,3,6,9,8,7,4,5 [1]Copy the code

Example 2

Input:

[]
Copy the code

The return value:

[]
Copy the code

Problem.

It is also a problem that can only be solved by traversal. I feel that this kind of mention does not require too much mathematical knowledge, and it is more friendly to novices.

The problem is that we want to traverse an array in a clockwise spiral. As I think about it, it seems impossible to traverse the array in one loop. We must have four smaller loops to traverse the edges of the square under one larger loop.

Times 1, 2, 3, 4, 5, 6, 7, 8, 9Copy the code

Divide the array to spiral into a circle, first spiral through the outer circle, and then to the inner circle, showing a trend to shrink inward.

So you go 1-2-3-6-9-8-7-4, and then you go to 5.

So how do I traverse the outer circle?

We need to have a coordinate (x,y), and we go through the upper border: 1-2-3; Then go through the right border again: 6, there is no 9;

Run through the bottom border: 9-8-7, and finally the left border: 4

The picture is a little “delicate”, don’t worry.

We need to store the top, bottom, and left borders in a variable, such as the first border of a 3*3 array. Top (0) and bottom(2) locate the first and third lines, respectively. The former is traversed to the right and the latter is traversed to the left. y = top/bottom

Top < y < bottom, x = left/right

After completing the border loop, all ++/–, shrink the borders

So when you get to the innermost layer, you either have a perfectly good square, or you have a single number, like in the example above, there’s only a 9 in the middle, and in the example below, there’s a square right next to each other.

So how do these two things work together?

In order to be compatible with these two cases, the top and bottom borders are traversed at one time, that is, 1-0-1-2 and 5-6-7-2 are traversed at one time, and the left and right borders are traversed only the middle part, excluding the beginning and end.

There’s also the loop boundary problem, where we need to find the last inner border, which is when we’ve already traversed the last border.

Times 1, 2, times 3, 4Copy the code

Let’s take a second order array and find the bounds of the loop.

So top(0),bottom(1),left(0),right(1).

When the loop is complete, the bounds are indented: top++,bottom–,right–,left++.

top(1),bottom(0),left(1),right(0)

Stop the loop when top < bottom or left > right.

The general idea is like this, specific knock code encounter and then solve.

code

public ArrayList<Integer> spiralOrder(int[][] matrix) { ArrayList<Integer> result = new ArrayList<Integer>(); if (matrix.length == 0 || matrix[0].length == 0) { return result; } // int top = 0, bottom = matrix.length - 1; int left = 0, right = matrix[0].length - 1; Int x = 0, y = 0; while (top <= bottom && left<=right) { for (x = left - 1, y = top; x < right; ) {// move to the right x++; result.add(matrix[y][x]); For (x = right, y = top + 1; x = right, y = top + 1; y < bottom; ++) {result.add(matrix[y][x]); {{1,2,3,4}},{{1},{2},{3},{4}},{{1},{2},{3},{4}} */ for (x = right+1, y = bottom; top ! = bottom && x > left; ) { x--; Result. add(matrix[y][x]); } for (x = left, y = bottom-1; left ! = right && y > top; Y --) {// add result.add(matrix[y][x]); } // shrink boundaries top++; bottom--; right--; left++; } return result; }Copy the code

Run!

The last

This is the cattle guest on the last entry level of the algorithm, I personally feel that do down or a little difficult, it seems that the algorithm is still a long way, come on.

So that’s my algorithm for today.

Here is a programmer Xu Xiaobai, daily algorithm [is] my new open a column, primary record my daily learning algorithm, here also hope that I can stick to the daily learning algorithm, don’t know whether this article style you like, don’t mean you free praise, your thumb up, collection, and comments are after work I insist on more power.