Share my Java method without extra space for swap


  • 1
    M
    public class Solution {
        public void rotate(int[][] matrix) {
            if (matrix == null) return ;
            int n = matrix.length;
            if (n < 2) return ;
            int i = 0, j = 0;
            for (; i < n; i++)
                for (j = 0; j < n - 1 - i; j++) {
                    matrix[i][j] ^= matrix[n - 1 - j][n - 1 -i];
                    matrix[n - 1 - j][n - 1 - i] ^= matrix[i][j];
                    matrix[i][j] ^= matrix[n - 1 - j][n - 1 - i];
                }
            for (i = 0, j = n - 1; i < j; i++, j--)
                for (int k = 0; k < n; k++) {
                    matrix[i][k] ^= matrix[j][k];
                    matrix[j][k] ^= matrix[i][k];
                    matrix[i][k] ^= matrix[j][k];
                }
        }
    }
    

    I swap two elements by means of 'Xor' operation. Aha, it's really 'in place'.


  • 0
    Y

    My solution is similar to yours.
    The index relationship of original and rotated matrix is

    1. (i, j) -----> (j, n-1-j)
    2. First step: (i, j) -----> (j, i) This step is transpose转置 The 1st for loop in the code below
    3. Second step: (j, i) -----> (j, n-1-i) This step is 左右镜面交换 The 2nd for loop in the code below

    Note: Using XOR to swap two element is excellent idea!

    public void rotate(int[][] matrix) {
            if (matrix == null) return;
            int n = matrix.length;
            if (n<2) return;
    
        
        
        for (int i=0; i<n-1; i++){
        	for (int j=i+1; j<n; j++){
        		matrix[i][j] ^= matrix[j][i];
        		matrix[j][i] ^= matrix[i][j];
        		matrix[i][j] ^= matrix[j][i];
        	}
        }
        
        for (int i=0; i<n; i++){
        	for (int j=0; j<matrix.length/2; j++){
        		matrix[i][j] ^= matrix[i][n-1-j];
        		matrix[i][n-1-j] ^= matrix[i][j];
        		matrix[i][j] ^= matrix[i][n-1-j];
        	}       	
        }    
    }

Log in to reply
 

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