rotate an 2D matrix by 90 degrees (clockwise)
[
[1,2,3],
[4,5,6],
[7,8,9]
]
==>
[
[7,4,1],
[8,5,2],
[9,6,3]
]
[
[1, 2, 3, 4]
[5, 6, 7, 8]
[9, 10,11,12]
[13,14,15,16]
]
2. Implementation
Complexity:Time: O(m*n) Space:O(1) in-place
keep 1
1->7[2,0]
7->9[,2,2]
9->3[0,2]
3-> 1[0,0]
keep2
2->4[1,0]
4->8[2,1]
8->6[1,2]
6-> 2 [0,1]
Q1: how many times?
A1: for n/2 layer, we do n/2 number of times rotate for each layer, they follow the same rule
Q1: how to iterate?
A1: we iterate to the element before boundary element (not included)
FOLLOW UP: What if a matrix nxm matrix, which means not square matrix?
// Time:O(m*n), Space:O(1) public void rotate (int[][] matrix) { // validate the input if ( matrix == null || matrix.length ==0 || matrix[0].length ==0) { return; } int layer = n >>1; for (int row = 0 ; row < layer; row++) { // NOTE: col start from layer for (int col = row ; col < matrix[0].length-1;col++ ) { // NOTE: the first element for each layer (row index) // 4 value (4 corner) top<-left data-blogger-escaped--="" data-blogger-escaped--col="" data-blogger-escaped-1="" data-blogger-escaped-bottom="" data-blogger-escaped-col="" data-blogger-escaped-int="" data-blogger-escaped-matrix.legnth-1="" data-blogger-escaped-matrix="" data-blogger-escaped-right="" data-blogger-escaped-row="" data-blogger-escaped-temp="matrix[row][col];" data-blogger-escaped-top=""> 7 4 1, col has sth to do with row, cur ROW== next COL matrix[(matrix.length-1) - col][row] = matrix[(matrix.length-1)-row][(matrix.length-1) - col];// e.g., 7 8 9 (bottom)-> 7 8 9(left), row has sth to do with col, cur ROW==next COL matrix[(matrix.length-1)-row][(matrix.length-1) - col] = matrix[col][(matrix.length-1)-row];// e.g., 3,6,9 => 9,6,3, col ~ row, cur ROW==next COL matrix[col][(matrix.length-1)-row] = temp;// 1,2,3(top)->1,2,3(right) } } }// 1234 // 5678 //=> // 51 // 62 // 73 // 84
public int[][] rotate(int[][] matrix) { // NOTE: there is no way to do in-place, so create a new matrix int[][] newmatrix = new int[matrix[0].length][mtrix.length]; // validate the input if ( matrix == null || matrix.length ==0 || martix[0].length == 0) return newmatrix; for (int i = 0; i < matrix.length; i++) for (int j = 0 ; j < matrix[0].length; j++) newmarix[j][(matrix.length-1) - i] = matrix[i][j]; return newmatrix; }3. Similar Ones
Spiral Matrix I
Spiral Matrix II
http://www.careercup.com/question?id=5667482614366208
No comments:
Post a Comment