经典算法面试题目-置矩阵行列元素为0(1.7)-阿里云开发者社区

开发者社区> 谙忆> 正文

经典算法面试题目-置矩阵行列元素为0(1.7)

简介: 题目 Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0. 写一个函数处理一个MxN的矩阵,如果矩阵中某个元素为0,那么把它所在的行和列都置为0. 解答 简单题。
+关注继续查看

题目

Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0.

写一个函数处理一个MxN的矩阵,如果矩阵中某个元素为0,那么把它所在的行和列都置为0.

解答

简单题。遍历一次矩阵,当遇到元素等于0时,记录下这个元素对应的行和列。
可以开一个行数组row和列数组col,当元素a[i][j]等于0时, 就把row[i]和col[j]置为1。
第二次遍历矩阵时,当某个元素对应的行row[i] 或列col[j]被设置为1,说明该元素在需要被置0的行或列上,因此将它(行/列)置0。

代码如下:

#include <iostream>
#include <cstring>
using namespace std;

void zero(int a[5][5], int m, int n){
    bool row[m], col[n];
    memset(row, 0, sizeof(row));
    memset(col, 0, sizeof(col));
    for(int i=0; i<m; ++i)
        for(int j=0; j<n; ++j)
            if(a[i][j] == 0){
                row[i] = true;
                col[j] = true;
            }
    for(int i=0; i<m; ++i)
        for(int j=0; j<n; ++j)
            if(row[i] || col[j])
                a[i][j] = 0;
}


int main()
{
    int a[5][5] = {
        {1, 2, 3, 4,5},
        {5, 6, 0, 7,8},
        {9, 0, 1, 1,2},
        {3, 4, 1, 1,9},
        {4, 3, 0, 6,9}
    };
     for(int i=0; i<5; ++i){
        for(int j=0; j<5; ++j)
            cout<<a[i][j]<<" ";
        cout<<endl;
    }
    cout<<endl;

    zero(a, 5, 5);
     for(int i=0; i<5; ++i){
        for(int j=0; j<5; ++j)
            cout<<a[i][j]<<" ";
        cout<<endl;
    }
    cout<<endl;
    return 0;
}

输出结果:

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
数据分析与挖掘的经典算法
最近看到一篇文章介绍了数据分析与挖掘的十大经典算法:C4.5,K-Means,SVM,Apriori,EM,PageRank,AdaBoost,KNN,Native Bayes,CART。
2365 0
Algorithm:树相关算法(BBT/BST/B树/R树)简介(二叉查找树、二叉查找树的插入节点、二叉查找树的删除、二叉树的遍历、平衡二叉树)C 语言实现
Algorithm:树相关算法(BBT/BST/B树/R树)简介(二叉查找树、二叉查找树的插入节点、二叉查找树的删除、二叉树的遍历、平衡二叉树)C 语言实现
19 0
任务调度:时间轮算法经典案例解析及应用实现
平时大家的工作中应该会遇到较多需要在某个时间点执行某个任务,比如对运维来说,定时数据库的备份,日志和监控信息的抓取;比如业务系统,某个时间点给某个人群用户发放优惠券,甚至从操作系统角度,人机交互进程、视频播放的实时进程、批处理的后台进程等进程间的调度。。。 所以如何将这些任务高效、精准的调度?是任务调度系统中最重要的命题,当然在业务系统中一个完善的任务调度系统是很复杂的,需要具备能调度、可视化管理、过程可追溯、结果可分析、持久化、高可用等特性,这篇文章主要讨论任务调度逻辑,其余的内容我们后面文章探讨。
123 0
【算法导论】第i小的元素
第i小的元素       时间复杂度:O(n).       基本思想:和快速排序的思想相似,也是对数组进行递归划分,但是有所差别的是,快速排序会递归处理划分的两边,而随机化的选择算法只选择一边。
744 0
经典算法面试题目-矩阵旋转90度(1.6)
题目 Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place? 一张图像表示成NxN的矩阵,图像中每个像素是4个字节,写一个函数把图像旋转90度。
2225 0
经典算法详解(11)递归查找数组中的最大值
题目:编写一个程序,用递归的方法实现查找数组中的最大值。 C++实现 1 #include 2 3 using namespace std; 4 //第一种方法是常规方法,不是使用递归,首先将第一个元素的值赋值给max,然后遍历数组, 5 //当遇到超高max的值时将其赋值给max,最...
1354 0
[leetcode/lintcode 题解] 算法面试真题:BST的中序前驱节点
[leetcode/lintcode 题解] 算法面试真题:BST的中序前驱节点
193 0
经典算法面试题目-置矩阵行列元素为0(1.7)
题目 Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0. 写一个函数处理一个MxN的矩阵,如果矩阵中某个元素为0,那么把它所在的行和列都置为0. 解答 简单题。
869 0
经典算法详解(10)图中有多少个三角形
题目:请说出下面图形中包含多少个三角形?请用一个程序完成计算。 C++版本 1 #include 2 3 using namespace std; 4 5 const char NO_POINT = '0'; 6 7 //任意的一条线 8 const char *map[]...
3701 0
+关注
谙忆
GitHub: https://github.com/chenhaoxiang
714
文章
40
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载