当前位置：首页 > article >正文

【力扣Hot 100】矩阵2

article 2025/1/26 21:44:15

旋转图像：观察旋转前后矩阵，发现点 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;
    }
};