C ++程序中最大子矩阵面积为1的计数比0的计数大

在这个问题中,我们得到一个大小为nXn的二维矩阵,其中包含二进制数(0/1)。我们的任务是创建一个程序,以找到最大子矩阵区域,该区域的计数为1的点数大于0的数。

让我们举个例子来了解这个问题,

输入项

bin[N][N] = {

   {0, 1, 0, 0},

   {1, 1, 0, 0},

   {1, 0, 1, 1},

   {0, 1, 0, 1}

}

输出结果

9

说明

submatrix :

bin[1][0], bin[1][1], bin[1][2]

bin[2][0], bin[2][1], bin[2][2]

bin[3][0], bin[3][1], bin[3][2]

is the largest subarray with more 1’s one more than 0’s.

Number of 0’s = 4

Number of 1’s = 5

解决方法

一种简单的方法是从矩阵中找到所有可能的子矩阵,然后从所有矩阵中返回最大面积。

这种方法易于思考和实现,但是要花费大量时间,并且需要嵌套循环,从而使时间复杂度为O(n ^ 4)。因此,让我们讨论另一种更有效的方法。

这里的想法是将列固定在矩阵的左右两边,然后找到最大的子数组,该子数组的数字为0的数字大于1的数字。我们将计算每一行的总和,然后将其累加。查找计数为1的最大区域多于0的数目。

示例

该程序说明了我们解决方案的工作原理,

#include <bits/stdc++.h>

using namespace std;

#define SIZE 10

int lenOfLongSubarr(int row[], int n, int& startInd, int& finishInd){

   unordered_map<int, int> subArr;

   int sumVal = 0, maxSubArrLen = 0;

   for (int i = 0; i < n; i++) {

      sumVal += row[i];

      if (sumVal == 1) {

         startInd = 0;

         finishInd = i;

         maxSubArrLen = i + 1;

      }

      else if (subArr.find(sumVal) == subArr.end())

         subArr[sumVal] = i;

      if (subArr.find(sumVal − 1) != subArr.end()) {

         int currLen = (i − subArr[sumVal − 1]);

         if (maxSubArrLen < currLen)

            startInd = subArr[sumVal − 1] + 1;

         finishInd = i;

         maxSubArrLen = currLen;

      }

   }

   return maxSubArrLen;

}

int largestSubmatrix(int bin[SIZE][SIZE], int n){

   int rows[n], maxSubMatArea = 0, currArea, longLen, startInd,

   finishInd;

   for (int left = 0; left < n; left++) {

      memset(rows, 0, sizeof(rows));

      for (int right = left; right < n; right++) {

         for (int i = 0; i < n; ++i){

            if(bin[i][right] == 0)

               rows[i] −= 1;

            else

               rows[i] += 1;

         }

         longLen = lenOfLongSubarr(rows, n, startInd, finishInd);

         currArea = (finishInd − startInd + 1) * (right − left + 1);

         if ((longLen != 0) && (maxSubMatArea < currArea)) {

            maxSubMatArea = currArea;

         }

      }

   }

   return maxSubMatArea;

}

int main(){

   int bin[SIZE][SIZE] = {

      { 1, 0, 0, 1 },

      { 0, 1, 1, 1 },

      { 1, 0, 0, 0 },

      { 0, 1, 0, 1 }

   };

   int n = 4;

   cout<<"The maximum sub−matrix area having count of 1’s one more

   than count of 0’s is "<<largestSubmatrix(bin, n);

   return 0;

}

输出结果

The maximum sub-matrix area having count of 1’s one more than count of

0’s is 9

以上是 C ++程序中最大子矩阵面积为1的计数比0的计数大 的全部内容, 来源链接: utcz.com/z/315944.html

回到顶部