C++实现LeetCode(73.矩阵赋零)

[LeetCode] 73.Set Matrix Zeroes 矩阵赋零

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

click to show follow up.

Follow up:

Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

据说这题是CareerCup上的原题，我还没有刷CareerCup，所以不知道啦，不过这题也不算难，虽然我也是看了网上的解法照着写的，但是下次遇到绝对想的起来。这道题中说的空间复杂度为O(mn)的解法自不用多说，直接新建一个和matrix等大小的矩阵，然后一行一行的扫，只要有0，就将新建的矩阵的对应行全赋0，行扫完再扫列，然后把更新完的矩阵赋给matrix即可，这个算法的空间复杂度太高。将其优化到O(m+n)的方法是，用一个长度为m的一维数组记录各行中是否有0，用一个长度为n的一维数组记录各列中是否有0，最后直接更新matrix数组即可。这道题的要求是用O(1)的空间，那么我们就不能新建数组，我们考虑就用原数组的第一行第一列来记录各行各列是否有0.

- 先扫描第一行第一列，如果有0，则将各自的flag设置为true
- 然后扫描除去第一行第一列的整个数组，如果有0，则将对应的第一行和第一列的数字赋0
- 再次遍历除去第一行第一列的整个数组，如果对应的第一行和第一列的数字有一个为0，则将当前值赋0
- 最后根据第一行第一列的flag来更新第一行第一列

代码如下：

class Solution {
public:
    void setZeroes(vector<vector<int> > &matrix) {
        if (matrix.empty() || matrix[0].empty()) return;
        int m = matrix.size(), n = matrix[0].size();
        bool rowZero = false, colZero = false;
        for (int i = 0; i < m; ++i) {
            if (matrix[i][0] == 0) colZero = true;
        }
        for (int i = 0; i < n; ++i) {
            if (matrix[0][i] == 0) rowZero = true;
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (matrix[0][j] == 0 || matrix[i][0] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (rowZero) {
            for (int i = 0; i < n; ++i) matrix[0][i] = 0;
        }
        if (colZero) {
            for (int i = 0; i < m; ++i) matrix[i][0] = 0;
        }
    }
};

到此这篇关于C++实现LeetCode(73.矩阵赋零)的文章就介绍到这了,更多相关C++实现矩阵赋零内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(66.加一运算)

    [LeetCode] 66. Plus One 加一运算 Given a non-empty array of decimal digits representing a non-negative integer, increment one to the integer. The digits are stored such that the most significant digit is at the head of the list, and each element in the a

  • C++实现LeetCode(63.不同的路径之二)

    C++实现LeetCode(63.不同的路径之二)

    [LeetCode] 63. Unique Paths II 不同的路径之二 A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right c

  • C++实现LeetCode(70.爬楼梯问题)

    [LeetCode] 70. Climbing Stairs 爬楼梯问题 You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Note: Given n will be a positive integer. Examp

  • C++实现LeetCode(62.不同的路径)

    C++实现LeetCode(62.不同的路径)

    [LeetCode] 62. Unique Paths 不同的路径 A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner

  • C++实现LeetCode(64.最小路径和)

    [LeetCode] 64. Minimum Path Sum 最小路径和 Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in t

  • C++实现LeetCode(67.二进制数相加)

    [LeetCode] 67. Add Binary 二进制数相加 Given two binary strings a and b, return their sum as a binary string. Example 1: Input: a = "11", b = "1" Output: "100" Example 2: Input: a = "1010", b = "1011" Output: &q

  • C++实现LeetCode(174.地牢游戏)

    [LeetCode] 174. Dungeon Game 地牢游戏 The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the t

  • C++实现LeetCode(68.文本左右对齐)

    [LeetCode] 68.Text Justification 文本左右对齐 Given an array of words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified. You should pack your words in a greedy approach; that i

  • C++实现LeetCode(73.矩阵赋零)

    [LeetCode] 73.Set Matrix Zeroes 矩阵赋零 Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place. click to show follow up. Follow up: Did you use extra space? A straight forward solution using O(mn) space is probably

  • python中numpy矩阵的零填充的示例代码

    python中numpy矩阵的零填充的示例代码

    目录 需求: 一.再new一个更大的所需要的矩阵大小 二.pad函数 其他想法 需求: 对于图像处理中的一些过程,我需要对读取的numpy矩阵进行size的扩充,比如原本是(4,6)的矩阵,现在需要上下左右各扩充3行,且为了不影响数值计算,都用0填充. 比如下图,我有一个4x5大小的全1矩阵,但是现在我要在四周都加上3行的0来扩充大小,最后扩充完还要对原区域进行操作. 方法: 想到了几种方法,记录一下. 一.再new一个更大的所需要的矩阵大小 a = np.ones((4,5)) #假设原矩阵是

  • C++实现LeetCode数组练习题

    目录 1.存在重复元素 2.最大子序和 3.两数之和 4.合并两个有序数组 5.两个数组的交集II 6.买卖股票的最佳时机 7.杨辉三角 8.重塑矩阵 9.有效的数独 10.矩阵置零 总结 1.存在重复元素 排序数组,之后遍历是否有重复的元素 public boolean containsDuplicate(int[] nums) { Arrays.sort(nums); for(int i=1;i<nums.length;i++){ if(nums[i-1]==nums[i]){ return

  • 浅谈c/c++中使用指针需要注意的问题

    一.使用指针的时候需要注意几点: • 分配空间 • 初始化 • 释放 二.常见的错误有几种: 1)内存分配未成功,却使用了它 编程新手常犯这种错误,因为他们没有意识到内存分配会不成功.常用解决办法是,使用内存之前检查指针是否为Null. 如果指针p是函数的参数,那么在函数的入口处用assert(p != NULL)进行检查.如果使用malloc或new来申请内存,应该用if(p == NULL)或if(p != NULL)进行放错处理. 2)内存分配虽然成功,但是尚未初始化就引用它 犯这种错误主

  • 浅谈C++内存分配及变长数组的动态分配

    第一部分 C++内存分配 一.关于内存 1.内存分配方式 内存分配方式有三种: (1)从静态存储区域分配.内存在程序编译的时候就已经分配好,这块内存在程序的整个运行期间都存在 例如全局变量,static变量. (2)在栈上创建.在执行函数时,函数内局部变量的存储单元都可以在栈上创建,函数执行结束时这些存 储单元自动被释放.栈内存分配运算内置于处理器的指令集中,效率很高,但是分配的内存容量有限. (3) 从堆上分配,亦称动态内存分配.程序在运行的时候用malloc或new申请任意多少的内存,程序员

  • 老生常谈C/C++内存管理

    内存分配方式 简介 在C++中,内存分成5个区,他们分别是堆.栈.自由存储区.全局/静态存储区和常量存储区. 栈:在执行函数时,函数内局部变量的存储单元都可以在栈上创建,函数执行结束时这些存储单元自动被释放.栈内存分配运算内置于处理器的指令集中,效率很高,但是分配的内存容量有限. 堆:就是那些由 new分配的内存块,他们的释放编译器不去管,由我们的应用程序去控制,一般一个new就要对应一个 delete.如果程序员没有释放掉,那么在程序结束后,操作系统会自动回收. 自由存储区:就是那些由mall

  • Opencv2.4.9函数HoughLinesP分析

    Opencv2.4.9函数HoughLinesP分析

    标准霍夫变换本质上是把图像映射到它的参数空间上,它需要计算所有的M个边缘点,这样它的运算量和所需内存空间都会很大.如果在输入图像中只是处理m(m<M)个边缘点,则这m个边缘点的选取是具有一定概率性的,因此该方法被称为概率霍夫变换(Probabilistic Hough Transform).该方法还有一个重要的特点就是能够检测出线端,即能够检测出图像中直线的两个端点,确切地定位图像中的直线. HoughLinesP函数就是利用概率霍夫变换来检测直线的.它的一般步骤为: 1.随机抽取图像中的一个特

  • java的多线程高并发详解

    java的多线程高并发详解

    1.JMM数据原子操作 read(读取)∶从主内存读取数据 load(载入):将主内存读取到的数据写入工作内存 use(使用):从工作内存读取数据来计算 assign(赋值):将计算好的值重新赋值到工作内存中 store(存储):将工作内存数据写入主内存 write(写入):将store过去的变量值赋值给主内存中的变量 lock(锁定):将主内存变量加锁,标识为线程独占状态 unlock(解锁):将主内存变量解锁,解锁后其他线程可以锁定该变量 2.来看volatile关键字 (1)启动两个线程

  • Java基础之创建虚拟机对象的过程详细总结

    Java基础之创建虚拟机对象的过程详细总结

    一.对象的创建 1.1 new 类名 虚拟机遇到一条new指令时,首先检查这个指令的参数是否能在常量池中定位到一个类的符号引用,并检查这个符号引用代表的类是否已经被加载.解析和初始化过.如果没有,先执行相应的类加载过程. 1.2 分配内存 虚拟机为新生对象分配内存.对象所需内存大小在类加载完成后就可以确定,为对象分配内存等同于把一块确定大小的内存从Java堆中划分出来. (1)内存分配的方式有两种: ① 指针碰撞: java堆如果规整,一边是用过的内存,一边是空闲的内存,中间一个指针作为边界指示

  • 新手入门Jvm-- JVM对象创建与内存分配机制

    新手入门Jvm-- JVM对象创建与内存分配机制

    1. 对象的创建 对象创建的主要流程: 1.类加载检查 虚拟机遇到一条new指令时,首先将去检查这个指令的参数是否能在常量池中定位到一个类的符号引用,并且检查这个符号引用代表的类是否已被加载.解析和初始化过.如果没有,那必须先执行相应的类加载过程. new指令对应到语言层面上讲是,new关键词.对象克隆.对象序列化等. 2.分配内存 在类加载检查通过后,接下来虚拟机将为新生对象分配内存.对象所需内存的大小在类 加载完成后便可完全确定,为对象分配空间的任务等同于把 一块确定大小的内存从Java堆中

随机推荐