矩阵旋转问题
顺时针旋转矩阵
http://www.nowcoder.com/questionTerminal/2e95333fbdd4451395066957e24909cc
- 方法一：开辟n*n空间的矩阵，将原矩阵中的数据赋值到新建的矩阵中，空间复杂度为O(n^2)。
- 方法二：利用原矩阵中数据的范围为0-300的条件，数据仅利用了int类型32位中的低9位，因此可以利用高位来存新值，低9位存旧值，空间复杂度为O(1)。个人觉得面试这么写才行，线性代数矩阵变换那一套面试官不一定觉得你具备计算机思维能力。
import java.util.*; public class Rotate { public int[][] rotateMatrix(int[][] mat, int n) { // write code here // 原地算法，空间复杂度为O(1) for(int i = 0; i < n; ++i){ for(int j = 0; j < n; ++j){ mat[j][n - i - 1] += ((mat[i][j] & 0b111111111) << 9); } } for(int i = 0; i < n; ++i){ for(int j = 0; j < n; ++j){ mat[i][j] >>= 9; } } return mat; } }
