思路如下:
利用i, j 将二维数组的所有节点遍历一遍
利用m, n将以[i][j]为左上顶点的子矩阵遍历一遍
判断i, j, m, n四个变量确定的矩阵是否为全1矩阵
代码实现:
int numSubmat...看一下时间复杂度呢? 一眼就看到了函数里的六层循环, 么的说, O(n^6).
这时, 我大哥说他的时间复杂度是 O(n^3). 那我这小心情, 必须整出来, 再想....在最后判断是否全1的循环中, 如果左上的数字是0, 那必然没有全1子矩阵了
再如果向下找的时候, 碰到0, 那下一列的时候也没必要超过这里了, 因为子矩阵至少有一个0了, 如下图:
?...再看看现在的时间复杂度. O(n^4); 比刚才的六次方, 直接降了两个数量级. 但是比我大哥还差点意思哈.
方案三
打扰了, 没有想到O(n^3)的解法. 经过我哥的一番指点, 可以说是豁然开朗....算法题偶尔做做还挺好的, 也不需要很高深的数学知识, 还可以锻炼思维, 蛮有趣的, 之后可以抽时间来看看, 嘿嘿.