LeetCode Rust - 48 - 旋转图像
解一，模拟旋转
暴力模拟，懒得写
解二，翻转两次
- 先沿着左下到右上的对角线左右翻转
- 从左下角的元素开始，将该元素上方和右侧的项依次交换位置
- 再验证水平中线上下翻转
pub fn rotate(matrix: &mut Vec<Vec<i32>>) {
let max_index = matrix.len() - 1;
let mut x = 0usize;
let mut y = max_index;
while x < max_index && y > 0 {
let mut i = x + 1;
let mut j = y - 1;
while i <= max_index && j >= 0 {
let tmp = matrix[y][i];
matrix[y][i] = matrix[j][x];
matrix[j][x] = tmp;
if j == 0 { break; } // usize 类型为非负数，再自减会报错，手动 break
i += 1;
j -= 1;
}
x += 1;
y -= 1;
}
for i in 0..max_index + 1 {
let mut top = 0usize;
let mut bottom = max_index;
while top < bottom {
let tmp = matrix[top][i];
matrix[top][i] = matrix[bottom][i];
matrix[bottom][i] = tmp;
top += 1;
bottom -= 1;
}
}
}
时间：$O(n^2)$
这里的 $n$ 是边长，每次翻转都要访问一遍所有元素，总共访问两次，宽松点就是 $n^2$，严格点是 $2n^2$
空间：$O(1)$