You need to enable JavaScript to run this app. Python删除矩阵全零行全零列 探索低于O(m*n)的优化方案
优惠活动
大模型
产品
解决方案
定价
更多

Python删除矩阵全零行全零列 探索低于O(m*n)的优化方案

矩阵全零行、全零列删除的Python实现

实现逻辑

  1. 标记所有需要保留的行:若某行存在至少一个非0元素,保留该行
  2. 基于已保留的行,标记所有需要保留的列:若某列在保留行中存在至少一个非0元素,保留该列

逻辑等价性说明:如果某列在原矩阵中是全0列,那么无论是否存在全0行,该列在保留行中的元素也全为0,必然会被标记为不保留;如果某列在原矩阵中存在非0元素,那么该非0元素所在的行必然不是全0行,会被纳入保留行范围,最终会被正确标记为需要保留。因此不需要遍历原矩阵所有行判断列是否全0,逻辑完全等价。

  1. 按保留的行、列索引提取元素,按指定格式输出

完整代码

# 读取矩阵行数、列数
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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.05 18:36:02