Python删除矩阵全零行全零列 探索低于O(m*n)的优化方案
矩阵全零行、全零列删除的Python实现
实现逻辑
- 标记所有需要保留的行:若某行存在至少一个非0元素,保留该行
- 基于已保留的行,标记所有需要保留的列:若某列在保留行中存在至少一个非0元素,保留该列
逻辑等价性说明:如果某列在原矩阵中是全0列,那么无论是否存在全0行,该列在保留行中的元素也全为0,必然会被标记为不保留;如果某列在原矩阵中存在非0元素,那么该非0元素所在的行必然不是全0行,会被纳入保留行范围,最终会被正确标记为需要保留。因此不需要遍历原矩阵所有行判断列是否全0,逻辑完全等价。
- 按保留的行、列索引提取元素,按指定格式输出
完整代码
# 读取矩阵行数、列数 m, n = map(int, input().split()) # 读取矩阵元素 matrix = [list(map(int, input().split())) for _ in range(m)] # 第一步:筛选需要保留的非全0行 keep_rows = [] for row in matrix: if any(val != 0 for val in row): keep_rows.append(row) # 第二步:基于保留的行,筛选需要保留的非全0列 # 初始化列标记,默认所有列都不保留 col_keep_flag = [False] * n for row in keep_rows: for col_idx, val in enumerate(row): if val != 0: col_keep_flag[col_idx] = True keep_cols = [idx for idx, flag in enumerate(col_keep_flag) if flag] # 第三步:按保留的列索引提取元素并输出 for row in keep_rows: output_row = [str(row[col_idx]) for col_idx in keep_cols] print(" ".join(output_row))
输入输出匹配验证
针对给出的输入示例:
4 4 1 0 3 4 0 0 0 0 4 0 6 8 4 0 2 4
代码运行后输出与示例完全一致:
1 3 4 4 6 8 4 2 4
时间复杂度问题说明
稠密存储场景(常规二维数组)
不存在低于O(mn)的实现方案。原因如下:
- 要判断某行是否全为0,必须遍历该行所有元素,少检查任何一个元素都无法确定该行是否存在非0值;
- 要判断某列是否全为0,本质上需要定位到所有非0元素的位置,在稠密存储下必须遍历所有矩阵元素才能完成该定位;
- 该问题的时间复杂度下界为Ω(mn),不存在比O(mn)更优的实现。
稀疏存储场景
当矩阵采用稀疏存储结构(仅保存非0元素的坐标和值,不存储大量0元素)时,时间复杂度可以远低于O(mn):
- 此时仅需要遍历所有k个非0元素,即可直接收集到所有存在非0值的行、列索引集合;
- 未出现在集合中的行、列即为全0行、全0列;
- 整体时间复杂度为O(k),当非0元素数量k远小于m*n时,复杂度会显著低于O(mn)。
内容的提问来源于stack exchange,提问作者Sohan Joshi
相关产品推荐
相关产品推荐

