【力扣Hot 100】矩阵2

旋转图像：观察旋转前后矩阵，发现点 i, j的变化规律，即每4个点会一同交换位置。遍历起始点。

搜索二维矩阵：按行二分法

3. 旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

!https://assets.leetcode.com/uploads/2020/08/28/mat1.jpg

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

!https://assets.leetcode.com/uploads/2020/08/28/mat2.jpg

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

提示：

• n == matrix.length == matrix[i].length
• 1 <= n <= 20
• 1000 <= matrix[i][j] <= 1000

题解

这一题最好在纸上打草稿。

首先，观察图像，发现：第 i 行第 j 列 会旋转到 第 j 行 倒数第 i 列

也就是 matrix[i, j] ⇒ matrix[j, n - i - 1]

按照上面的式子，就发现 matrix[j, n - i - 1] ⇒ matrix[n - i - 1, n - j - 1]

matrix[n - i - 1, n - j - 1] ⇒ matrix[n - j - 1, i]

matrix[n - j - 1, i] ⇒ matirx[i, j]

实现了闭环。也就是说，这四个点会绕一圈。所以，对于每4个点，我们都可以用下面这个式子来更新：

int temp = matrix[i][j];
matrix[i][j] = matrix[n - j - 1][i];
matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
matrix[j][n - i - 1] = temp;

对于应该列举哪个 i, j，可以画图，然后就会发现 i 会列举 0 ~ n / 2 （下取整，n 为奇数的时候，不用列举中间的那一行）

j 列举 0 ~ (n + 1) / 2 （上取整，n为奇数的时候，要列举中间那一列）

也可以 i , j 反过来，范围也是正确的。

代码：

class Solution {
public:void rotate(vector<vector<int>>& matrix) {int n = matrix.size();for(int i = 0; i < n / 2; i ++ ) {for(int j = 0; j < (n + 1) / 2; j ++ ) {int temp = matrix[i][j];matrix[i][j] = matrix[n - j - 1][i];matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];matrix[j][n - i - 1] = temp;}}}
};

4. 搜索二维矩阵

编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

示例 1：

!https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/11/25/searchgrid2.jpg

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

示例 2：

!https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/11/25/searchgrid.jpg

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• 109 <= matrix[i][j] <= 109
• 每行的所有元素从左到右升序排列
• 每列的所有元素从上到下升序排列
• 109 <= target <= 109

题解

我是一个喜欢偷懒的人，所以直接枚举每一行做二分

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {for(const auto& row : matrix) {int l = 0, r = matrix[0].size() - 1;while(l < r) {int mid = (l + r) >> 1;if(row[mid] >= target) r = mid;else l = mid + 1;}if(row[l] == target) return true;}return false;}
};