专栏首页烟草的香味计算矩阵中全1子矩阵的个数

计算矩阵中全1子矩阵的个数

前言

最近被我大哥安利了一道算法题, 这道题说难, 还不至于我做不出来, 说简单吧, 我还想不到最优解, 等把最优解告诉我之后, 我还正好能理解. 我甚至曾经怯怯的认为, 这题就是我哥专门给我找的, 嘿嘿, 心中说不出的小欢喜.

题来了, 此题出自力扣, 原题链接:

https://leetcode-cn.com/problems/count-submatrices-with-all-ones/

描述: 给你一个只包含 0 和 1 的 rows * columns 矩阵 mat ,请你返回有多少个 子矩形 的元素全部都是 1 。

例子:

输入:mat = [[1,0,1],
            [1,1,0],
            [1,1,0]]
输出:13
解释:
有 6 个 1x1 的矩形。
有 2 个 1x2 的矩形。
有 3 个 2x1 的矩形。
有 1 个 2x2 的矩形。
有 1 个 3x1 的矩形。
矩形数目总共 = 6 + 2 + 3 + 1 + 1 = 13 。

题意清晰明了, 开始尝试解题(使用 C 来进行解题).

方案一

首先直观上最先想到的, 就是穷举了. 一力破十会. 将所有出现的情况遍历一遍, 然后就能得出总数了. 思路如下:

  1. 利用i, j 将二维数组的所有节点遍历一遍
  2. 利用m, n将以[i][j]为左上顶点的子矩阵遍历一遍
  3. 判断i, j, m, n四个变量确定的矩阵是否为全1矩阵

代码实现:

int numSubmat(int** mat, int matSize, int* matColSize){
    int result = 0;
    // 遍历所有节点
    for (int i = 0; i < matSize; i++) {
        for (int j = 0; j < *matColSize; j++) {
            // 遍历当前节点为左上顶点的所有子矩阵
            for (int m = i; m < matSize; m++) {
                for (int n = j; n < *matColSize; n++) {
                    // 判断当前子矩阵是否为全1矩阵
                    int isOk = 1;
                    for (int p = i; p <= m; p++) {
                        for (int q = j; q <= n; q++) {
                            if(mat[p][q] != 1){
                                isOk = 0;
                                break;
                            }
                        }
                        if(!isOk) break;
                    }
                    // 计算总数
                    if(isOk) result++;
                }
            }
        }
    }
    return result;
}

随手写个测试用:

#include <stdio.h>
#include <stdlib.h>

int numSubmat(int** mat, int matSize, int* matColSize);

int main() {
    // 定义数组长度
    int matSize = 3, matColSize = 3;
    // 分配数组空间
    int **mat = (int **)malloc(matSize*sizeof(int*));
    // 动态分配内容
    for (int i = 0; i < matSize; i++) {
        mat[i] = (int *)malloc(matColSize*sizeof(int));
    }
    // 给数组填内容, 这里可以接收键盘数组
    mat[0][0] = 1;
    mat[0][1] = 0;
    mat[0][2] = 1;
    mat[1][0] = 1;
    mat[1][1] = 1;
    mat[1][2] = 0;
    mat[2][0] = 1;
    mat[2][1] = 1;
    mat[2][2] = 0;
    int result = numSubmat(mat, matSize, &matColSize);
    printf("%d", result);
    return 0;
}

执行过后, OK, 么的问题. 看一下时间复杂度呢? 一眼就看到了函数里的六层循环, 么的说, O(n^6).

这时, 我大哥说他的时间复杂度是 O(n^3). 那我这小心情, 必须整出来, 再想.

方案二

上面的六层循环中, 能不能想办法去掉一层呢? 有. 在最后判断是否全1的循环中, 如果左上的数字是0, 那必然没有全1子矩阵了

再如果向下找的时候, 碰到0, 那下一列的时候也没必要超过这里了, 因为子矩阵至少有一个0了, 如下图:

image-20200710234204779

在向右遍历的时候同理, 这样, 我们就可以确定, 所有遍历到的值都是1, 可以将判断全1的两层循环去掉. nice. 修改代码如下:

int numSubmat(int** mat, int matSize, int* matColSize){
    int result = 0;
    // 遍历所有节点
    for (int i = 0; i < matSize; i++) {
        for (int j = 0; j < *matColSize; j++) {
            if(mat[i][j] == 0) continue;
            int thisMaxColSize = *matColSize; // 当前向右最大值
            // 遍历当前节点为左上顶点的所有子矩阵
            for (int m = i; m < matSize; m++) {
                for (int n = j; n < thisMaxColSize; n++) {
                    if(mat[m][n] == 1) result++;
                    // 记录向右的最大值
                    else thisMaxColSize = n;
                }
            }
        }
    }
    return result;
}

OK, 经过测试完全么的问题. 再看看现在的时间复杂度. O(n^4); 比刚才的六次方, 直接降了两个数量级. 但是比我大哥还差点意思哈.

方案三

打扰了, 没有想到O(n^3)的解法. 经过我哥的一番指点, 可以说是豁然开朗. 思路不变. 上面的四层循环, 有没有什么办法能再减少一层呢?

想一下, 我们在第四层循环中, 向右遍历, 找的是什么? 是连续1的个数, 如果我们不用向右遍历, 直接就知道了这个连续1的个数, 那是不是就可以把这一层也省了呢?

那么问题来了, 如何不遍历就知道呢? 预处理. 在所有的遍历之前, 先进行一次遍历, 把每个节点向右的连续1个数计算好. 这个思路有点妙啊. 废话不多说, 再来:

int min(int a, int b){
    return a > b ? b : a;
}

int numSubmat(int** mat, int matSize, int* matColSize){
    // 进行预处理, 将每个节点向右的连续1个数算好(从右下向左上处理)
    for (int i = matSize - 1; i >= 0; i--) {
        for (int j = *matColSize - 1; j >= 0 ; j--) {
            if(mat[i][j] == 0) continue;
            // 最右侧不处理
            if(j == *matColSize-1) continue;
            // 每个节点的数字等于右边的加1
            mat[i][j] = mat[i][j+1] + 1;
        }
    }
    int result = 0;
    // 遍历所有节点
    for (int i = 0; i < matSize; i++) {
        for (int j = 0; j < *matColSize; j++) {
            if(mat[i][j] == 0) continue;
            int thisMaxColSize = *matColSize; // 当前向右最大值
            // 遍历当前节点为左上顶点的所有子矩阵
            for (int m = i; m < matSize; m++) {
                // 记录向右的最大值
                thisMaxColSize = min(thisMaxColSize, mat[m][j]);
                result += thisMaxColSize;
            }
        }
    }
    return result;
}

再看时间复杂度, 终于, O(n^3).


还有没有比三次方更快的解法呢? 可能..大概..或许有吧. 但是我想了好久也没有想到.

以上, 其实到第二个方案我都想到了, 但是最后一步怎么都没迈出去, 原因归结为做的少, 遇到的少. 算法题偶尔做做还挺好的, 也不需要很高深的数学知识, 还可以锻炼思维, 蛮有趣的, 之后可以抽时间来看看, 嘿嘿.

本文分享自微信公众号 - 烟草的香味(hujing-bc),作者:胡靖哥哥

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 微信朋友圈技术实现设想

    微信朋友圈是我们每天都在用的功能, 但是如果让你来实现一个微信朋友圈, 你会如何做呢? 我来简单设想一下。

    烟草的香味
  • 23种设计模式之代理模式

    代理模式是一个使用率非常高的模式,其定义为: 为其他对象提供一种代理以控制对这个对象的访问

    烟草的香味
  • MD文件图片base64自动编码

    不知道你在使用markdown写文章的时候有没有遇到过这样的烦恼, 文件写完了, 想将写完的文章粘贴到博客的时候, 你满心欢喜的复制粘贴, 但是发现图片根本复...

    烟草的香味
  • Codeforces Round #521 (Div. 3) D. Cutting Out(二分)

    题目链接:http://codeforces.com/contest/1077/problem/D

    Ch_Zaqdt
  • ZR18提高5解题报告

    设$f[i][j]$表示前$i$个位置,前缀和为$j$的方案数,转移的时候该位置放了什么,以及该位置之前的和是多少。

    attack
  • 1048 石子归并

    1048 石子归并 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 有n堆石子...

    attack
  • 2017.5.26暴力赛解题报告

    预计分数:T1:40AC+60TLE      T2:40AC+60TLE        T3:10AC+90TLE      总分=90 实际分数:T1:10...

    attack
  • HDU 1863 畅通工程

    一道很朴素的最小生成树,不过通过此题知道了,当n已经决定的情况下,若n个点无法构成最小生成树的话,最终得到ans无法得到精确的值,他会将无穷大的路径加入。 #i...

    用户1624346
  • 基础知识 | 每日一练(193)

    cout << boolalpha << ((i & (i - 1)) ? false : true) << endl;

    C语言入门到精通
  • Educational Codeforces Round 67 (Rated for Div. 2) A~E 贪心,构造,线段树,树的子树

    Educational Codeforces Round 67 (Rated for Div. 2)

    用户2965768

扫码关注云+社区

领取腾讯云代金券