2ms Java solution with comment: space O(1) and time O(n^2)


  • 0
    L
        public void rotate(int[][] matrix) {
            int n = matrix.length;
            int mid = (n + n % 2) / 2;  //total rounds to rotate
    
            //Rotate from the outermost edges to innermost edges
            for (int i = 0; i < mid; i++) {
                borderRoate(matrix, i, (n - 1) - i);
            }
        }
    
        /**
         * Rotate on the sub edges with the 4 concerns of below:
         *    [left, left]  ..   [left, right]
         *        ..                  ..
         *    [right,left]  ..  [right, right]
         *
         * The rotate sequence is: Top->Right->Bottom->Left->Top
         *
         * @param matrix
         * @param left  the left-top index
         * @param right the right-bottom index
         */
        private void borderRoate(int[][] matrix, int left, int right) {
            int rightEdge, bottomEdge, leftEdge;
    
            for (int i = 0; i < (right - left); i++) {
                //Right sub-edge
                rightEdge = matrix[left + i][right]; //back before overridden
                matrix[left + i][right] = matrix[left][left + i]; //Right <= Top
    
                //Bottom sub-edge
                bottomEdge = matrix[right][right - i];  //back before overridden
                matrix[right][right - i] = rightEdge;   //Bottom <=right
    
                //Left sub-edge
                leftEdge = matrix[right - i][left]; //back before overridden
                matrix[right - i][left] = bottomEdge;   //Left <=Bottom
    
                //Top sub-edge
                matrix[left][left + i] = leftEdge;  //Top <= Left
            }
        }
    

  • 0
    L

    @laqxs Now I provide the full class with simple test code. You can change the matrix length in main() method for checking.

    public class RotateImage {
    
        public void rotate(int[][] matrix) {
            int n = matrix.length;
            int mid = (n + n % 2) / 2;  //total rounds to rotate
    
            //Rotate from the outermost edges to innermost edges
            for (int i = 0; i < mid; i++) {
                borderRoate(matrix, i, (n - 1) - i);
            }
        }
    
        /**
         * Rotate on the sub edges with the 4 concerns of below:
         *    [left, left]  ..   [left, right]
         *        ..                  ..
         *    [right,left]  ..  [right, right]
         *
         * The rotate sequence is: Top->Right->Bottom->Left->Top
         *
         * @param matrix
         * @param left  the left-top index
         * @param right the right-bottom index
         */
        private void borderRoate(int[][] matrix, int left, int right) {
            int rightEdge, bottomEdge, leftEdge;
    
            for (int i = 0; i < (right - left); i++) {
                //Right sub-edge
                rightEdge = matrix[left + i][right]; //back before overridden
                matrix[left + i][right] = matrix[left][left + i]; //Right <= Top
    
                //Bottom sub-edge
                bottomEdge = matrix[right][right - i];  //back before overridden
                matrix[right][right - i] = rightEdge;   //Bottom <=right
    
                //Left sub-edge
                leftEdge = matrix[right - i][left]; //back before overridden
                matrix[right - i][left] = bottomEdge;   //Left <=Bottom
    
                //Top sub-edge
                matrix[left][left + i] = leftEdge;  //Top <= Left
            }
        }
    
        public static void main(String[] args) {
    
            //Change the matrix length to check the running result
            int length = 4;
            int[][] matrix = getMatrix(length);
            print(matrix);
    
            RotateImage ri = new RotateImage();
            ri.rotate(matrix);
            System.out.println("Rotated Result:");
            print(matrix);
        }
    
        /**
         * Generate a matrix for testing properties
         * @param length
         * @return
         */
        private static int[][] getMatrix(int length) {
            int[][] matrix = new int[length][length];
    
            for (int i = 1; i <= length; i++) {
                for (int j = 0; j < length; j++) {
                    matrix[j][i - 1] = i + j * 5;
                }
            }
    
            return matrix;
        }
    
        /**
         * Print the matrix
         * @param matrix
         */
        private static void print(int[][] matrix) {
            int length = matrix.length;
            for (int i = 0; i < length; i++) {
                for (int j = 0; j < length; j++) {
                    System.out.print("   " + matrix[i][j]);
                }
                System.out.println();
            }
        }
    }
    

    The console output for constant 4 is:
    1 2 3 4
    6 7 8 9
    11 12 13 14
    16 17 18 19
    Rotated Result
    16 11 6 1
    17 12 7 2
    18 13 8 3
    19 14 9 4

    Process finished with exit code 0


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.