今日矩阵系列

73.矩阵置0

解法一：使用标记数组

思想：

• 用两个数组来标识需要置为0的行和列

• 将标识的位置0

空间复杂度O(m+n)

解法二：使用标记变量

思想：

• 首先遍历数组的第一行和第一列，进行标记看是否需要置0

• 遍历抛开第一行和第一列的剩余元素，遇到0元素，就将所在第一行和第一列的对应位置置0，比如matrix[i][j] = 0, -》 matrix[i][0] = 0 && matrix[0][j] = 0，就是用第一行和第一列去充当标记数组

• 再遍历一遍除第一行和第一列外的剩余元素，把标记的行和列置0，matrix[i][0] = 0 || matrix[0][j] = 0

• 最后处理第一行和第一列

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        bool firstrow = false;
        bool firstcol = false;

        // 检查第一列
        for (int i = 0; i < matrix.size(); i++)
        {
            if (!matrix[i][0]) firstcol = true;
        }
        // 检查第一行
        for (int i = 0; i < matrix[0].size(); i++)
        {
            if (!matrix[0][i]) firstrow = true;
        }

        // 标记剩余行和列
        for (int i = 1; i < matrix.size(); i++)
        {
            for (int j = 1; j < matrix[0].size(); j++)
            {
                if(!matrix[i][j])
                {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }

        // 把被标记的行和列清零
        for (int i = 1; i < matrix.size(); i++)
        {
            for (int j = 1; j <matrix[0].size(); j++)
            {
                if (!matrix[i][0] || !matrix[0][j]) matrix[i][j] = 0;
            }
        }

        // 处理第一列
        if (firstcol)
        {
            for (int i = 0; i < matrix.size(); i++)
            {
                matrix[i][0] = 0;
            }
        }

        if (firstrow)
        {
            for (int j = 0; j < matrix[0].size(); j++)
            {
                matrix[0][j] = 0;
            }
        }
    }
};

空间复杂度O(1)

54.螺旋矩阵

按层模拟矩阵

考虑左闭右闭这样就不用再单独处理中间元素例如下图，如果左闭有开，就是转圈逻辑，中间的元素要单独去处理，如果是正方形就很方便，如果不是就很麻烦

我们使用左闭右闭，只考虑边界的变化，不要考虑开始坐标，但是要防止矩阵本身或者矩阵内围是一行或者一列的情况，所以转圈的时候要加上额外的条件，就是再处理剩余两个边界时，边界不能重合

        while (left <= right && top <= bottom)
        {
            for (int column = left; column <= right; column++)
            {
                res.push_back(matrix[top][column]);
            }
            for (int row = top + 1; row <= bottom; row++)
            {
                res.push_back(matrix[row][right]);
            }
            // 防止出现一行一列的重复添加的情况
            if (left < right && top < bottom)
            {
                for (int column = right - 1; column >= left; column--)
                {
                    res.push_back(matrix[bottom][column]);
                }
                for (int row = bottom -1; row > top; row--)
                {
                    res.push_back(matrix[row][left]);
                }
            }
            left++;
            right--;
            top++;
            bottom--;

48.旋转图像

原地修改矩阵：

• 将原数组沿着中轴对称翻转

• 然后沿着主对角线对称翻转

代码：

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int mid = matrix.size()/2;
        // 沿中轴翻转
        int r = 0;
        while(mid--)
        {
            for (int i = 0; i < matrix.size(); i++)
            {
                swap(matrix[r][i], matrix[matrix.size() - 1 - r][i]);
            }
            r++;
        }

        // 沿对角线翻转
        for (int i = 0; i < matrix.size(); i++)
        {
            for (int j = i + 1; j < matrix.size(); j++)
            {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
    }
};

240.搜索二维矩阵

题目描述：在矩阵中搜索目标数字，已知每一行每一列都是递增的。

解法：

1. 遍历整张图

2. 对每一行（或者列）二分

3. 从右上角z字形查找

Z字型查找

从右上角开始查找，不会漏掉任何一个区间，并且最大程度缩小搜索范围（要么向左，要么向下），时间复杂度最小

• 如果target小，就向左移动

• 如果target大，就向右移动

• 最差的情况，目标在左下角

代码：

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int i = 0;
        int j = matrix[0].size() - 1;
        while (i < matrix.size() && j >= 0)
        {
            if (matrix[i][j] > target) j--; // 向左移动
            else if (matrix[i][j] < target) i++;// 向下移动
            else return true;
        }
        return false;
    }
};