OD 算法题 B卷【矩阵稀疏扫描】

矩阵稀疏扫描

• 如果矩阵中的很多系数都为零，则为稀疏矩阵，给定一个矩阵，如果某行、列存在0的个数超出（包含）了行宽、列宽的一半（整除），则认为该行、列为稀疏的；
  

输入描述：
第一行输入m, n 表现行、列数；
后m行输入每行的数据；
输出描述:
第一行输出稀疏的行数；
第二行输出稀疏的列数；
示例1
输入：
3 3
1 0 0
0 1 0
0 0 1
输出：
3
3
示例2
输入：
5 3
-1 0 1
0 0 0
-1 0 0
0 -1 0
0 0 0
输出：
5
3
python实现：

• 计算每行、列0的总个数，并与行、列的一半进行比力；
  
• 时间复杂度                                        O                            (                                       n                               2                                      )                                  {O(n^2)}                     O(n2)
  

2. data = [int(x) for x in input().split(" ")]
3. m = data[0]
4. n = data[1]
6. rowZeroCount = [0 for x in range(m)]
7. colZeroCount = [0 for x in range(n)]
9. for i in range(m):
10.     input_arr = [int(x) for x in input().split(" ")]
11.     for j in range(n):
12.         if (input_arr[j] == 0):
13.             rowZeroCount[i]+=1
14.             colZeroCount[j]+=1
16. res1 = 0
17. for i in range(m):
18.     if rowZeroCount[i] >= int(n/2):
19.         res1+=1
20. print(res1)
22. res2= 0
23. for i in range(n):
24.     if colZeroCount[i] >= int(m/2):
25.         res2+=1
26. print(res2)

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

继续阅读请点击广告