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)$

data = [int(x) for x in input().split(" ")]
m = data[0]
n = data[1]rowZeroCount = [0 for x in range(m)]
colZeroCount = [0 for x in range(n)]for i in range(m):input_arr = [int(x) for x in input().split(" ")]for j in range(n):if (input_arr[j] == 0):rowZeroCount[i]+=1colZeroCount[j]+=1res1 = 0
for i in range(m):if rowZeroCount[i] >= int(n/2):res1+=1
print(res1)res2= 0
for i in range(n):if colZeroCount[i] >= int(m/2):res2+=1
print(res2)