This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

Spiral matrix

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

Tip:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100

Thought analysis

Following the clockwise traversal of the matrix, we can use a variable to control the upper, lower, left and right sides of the matrix. After each traversal, the corresponding value can be added or subtracted, and the traversal continues until the last node is known. The time complexity of the solution is O (n2) {O (n ^ 2)} O (n2), space complexity is O (1) (1)} {O O (1).

The code shown

Solution a: time complexity is O (n2) {O (n ^ 2)} O (n2), space complexity is O (1) (1)} {O O (1).

public List<Integer> spiralOrder(int[][] matrix) {
        int n = matrix.length;
        List<Integer> list = new ArrayList<>();
        
        int top = 0;
        int left = 0;
        int right = matrix[0].length - 1;
        int bottom = matrix.length - 1;

        int numEle = matrix[0].length * matrix.length;
        
        while(numEle > 0) {//top
            for(inti = left; i <= right && numEle >0; i++){ list.add(matrix[top][i]); numEle--; } top++;//right
            for(inti = top; i <= bottom && numEle >0; i++){ list.add(matrix[i][right]); numEle--; } right--;//bottom
            for(inti = right; i >= left && numEle >0; i--){ list.add(matrix[bottom][i]); numEle--; } bottom--;//left
            for(inti = bottom; i >= top && numEle >0; i--){ list.add(matrix[i][left]); numEle--; } left++; }return list;
    }
Copy the code

conclusion

Clockwise traversal matrix, in fact, the idea is not difficult, does it lie in the control of the boundary, deal with the boundary problem is very important.