48 Rotate Image
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up:
Could you do this in-place?
The Idea: Replace every row with the nth to last column respectfully.
Complexity: O(n) time and O(n) extra space
void rotate(vector<vector<int>>& matrix) {
int size = matrix.size();
vector<vector<int>> new_m(size, vector<int>(size));
// assuming nxn
int row = size - 1;
int col = 0;
for (int i = 0; i < size; i++) {
// bottom row = first column
for (int j = 0; j < size; j++) {
new_m[j][col] = matrix[row][j];
}
row--;
col++;
}
matrix = new_m;
}
The Idea: Reverse the matrix, and then swap on the
y=-x line of symmetry. ~~Notice that the diagonal swaps with itself, but that's not big deal. ~~We can alternatively reverse each column, and this would have the same effect as reversing the rows.
Complexity: O(n) time and O(1) spacevoid rotate(vector<vector<int>>& matrix) {
if (matrix.empty()) return;
reverse(matrix.begin(), matrix.end());
const size_t rows = matrix.size(), cols = matrix.at(0).size();
for (int i = 0; i < rows; i++) {
for (int j = i + 1; j < cols; j++) {
swap(matrix[i][j], matrix[j][i]);
}
}
}
Testing
int main() {
vector<vector<int>> matrix = {
{ 1,2,3,4 },
{ 5,6,7,8 },
{ 9,10,11,12 },
{ 13,14,15,16 },
};
rotate(matrix);
print2d(matrix);
}
Last modified 4yr ago