Thursday, January 8, 2015

Rotate Image

This is a very interesting question. In order to rotate the matrix in place, we need to adjust the value of each element. Think of what we should do to shift all elements left one position and put the first element in the last if it is a linear array:  we store the value of the first element and shift all other elements left, then put the value of the first element into the last position. The same thing here, the only difference is we need to determine the correct position.


The figure here shows how we should shift elements in a 3 * 3 matrix. We [0][0] -> [0][2] -> [2][2] -> [2][0] ->[0][0], generalize, [i][j] -> [j][n - i - 1] -> [n - i - 1][n - j - 1] -> [n - j - 1][i] -> [i][j], be careful about the bold part, otherwise some elements will be flipped upper side down, not rotated. 


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

No comments:

Post a Comment