1. Title Description

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

Case 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

2. How to solve the problem

Traverse a two-dimensional array from left to right, top to bottom, right to left, bottom to top.

public int[] spiralOrder(int[][] matrix) {
       if(matrix == null || matrix.length == 0) {return new int[0];
       }
       int top = 0,left = 0;
       int right = matrix[0].length - 1,bottom = matrix.length - 1;
       int[] res = new int[(right+1)*(bottom+1)];
       int k = 0;
       while(true) {// Left to right
        	for(intj = left; j <= right; j++){ res[k++] = matrix[top][j]; }if(++top > bottom)  break;
        	// From top to bottom
        	for(inti = top; i<=bottom; i++){ res[k++] = matrix[i][right]; }if(left > --right)  break;
        	// From right to left
        	for(intj = right; j>=left && top <= bottom; j--){ res[k++] = matrix[bottom][j]; }if(top > --bottom)  break;
        	// From bottom to top
        	for(inti=bottom; i>=top; i--){ res[k++] = matrix[i][left]; }if(++left > right)  break;
      }
   	  return res;
}
Copy the code

Algorithm analysis

  • Time complexity: O(Mn), m and n are the number of rows and columns of the matrix respectively
  • Space complexity: O(1), four bounds and array computed variables are the extra space of the usual size (res is the space that must be used)