LeetCode热题100——矩阵

73.矩阵清零

题目

给定一个 *m* x *n* 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

示例 1：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]

思路

第一次把满足条件的行和列用set存下来，第二次遍历即可，O(n^2)

代码如下：

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        unordered_set<int> a,b;
        for(int i = 0;i<matrix.size();i++){
            for(int j = 0;j<matrix[0].size();j++){
                if(matrix[i][j] == 0){
                    a.insert(i);
                    b.insert(j);
                }
            }
        }
        for(int i = 0;i<matrix.size();i++){
            for(int j = 0;j<matrix[0].size();j++){
                if(a.count(i) != 0 || b.count(j) != 0){
                    matrix[i][j] = 0;
                }
            }
        }
    }
};

54.螺旋矩阵

题目

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

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

示例 2：

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

思路

这个应该是很常见的一道题了，，，感觉频率很高，我习惯了一套模板就是把left，right，top和button确定下来，然后从左到右，从上到下，从右往左，从下往上遍历即可

代码如下：

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int left = 0,right = matrix[0].size()-1;
        int top = 0,button = matrix.size()-1;
        vector<int> ans;
        while(true){
            for(int i = left;i<right+1;i++){
                ans.emplace_back(matrix[top][i]);
            }
            top++;
            if(top > button) break;
            for(int i = top;i<button+1;i++){
                ans.emplace_back(matrix[i][right]);
            }
            right--;
            if(right < left) break;
            for(int i = right;i>left-1;i--){
                ans.emplace_back(matrix[button][i]);
            }
            button--;
            if(button < top) break;
            for(int i = button;i>top-1;i--){
                ans.emplace_back(matrix[i][left]);
            }
            left++;
            if(left > right)break;
        }
        return ans; 
    }
};

48.旋转图像

题目

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

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

示例 1：

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

示例 2：

输入：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]]

思路

因为不能使用另一个矩阵来记录，事实上很容易发现下标规律是[i,j] -> [j,n-1-i]，不过其实可以上下翻转一次再左上角和右下角翻转一次会是同样的效果，O(n^2)

代码如下：

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

240.搜索二维矩阵II

题目

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

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

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

示例 1：

输入：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：

输入：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

思路

发现规律，从右上角观察发现，利用i和j的加和减可以遍历整个矩阵

如果找到则返回true即可

代码如下：

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