Эң чоң аянты, 1 жана 0 сандарына барабар болгон тик бурчтуу суб-матрица


Кыйынчылык деңгээли катуу
Көп суралган Accenture Чындыгында Info Edge Monotype Solutions PayPal Pinterest Synopsys Times Internet UHG Optum
согуштук тизме Динамикалык программалоо Matrix

Маселени билдирүү

Nx m өлчөмүндөгү экилик матрица берилген. Маселе эң чоң аянтты 1 жана 0 сандарына барабар болгон тик бурчтуу суб-матрицаны табууда турат.

мисал

Dimensions = 4 x 4
Matrix:
1 1 1 1
0 1 0 1
1 0 1 0
1 0 0 0
12

Түшүндүрмө: Эгерде (0,1), (0,3), (3,1) жана (3,3) бурчтары бар субматрицаны карасак. Бул суб-матрица эң чоң төрт бурчтуу суб-матиксти түзөт, анын саны 0 жана 1 секцияларына барабар.

Dimesnions = 2 x 4
Matrix:
0 0 1
0 1 1
6

Түшүндүрмө: Баштапкы матрицада 0s менен 1s бирдей санда болгондуктан, баштапкы матрица биздин жооп болот. Бул жерде ушундай.

жакындоо

Naive Appocach

Биздин колубуздан келген эң оңой нерсе, төрт багыт боюнча суб-матрицанын көрсөткүчтөрү боюнча ар биринин төрт көрсөткүчүн карап чыгуу. Биз суб-матрицаны бекиткенде, 0 жана 1 сандарын эсептей алабыз. Бирок бул натыйжалуу ыкма эмес жана убакыттын чектелгендигинен ашып кетет. Ар бир 0ну -1 менен алмаштырсак, көйгөйдү бир аз оптималдаштыра алабыз. Андан кийин, 2D префикси суммасы техникасын колдонуп, суб-матрицанын суммасын табабыз. Бирок муну колдонуу жетиштүү болбойт да.

Натыйжалуу мамиле

Матрицанын ар бир 0сун терс 1 менен алмаштыруу натыйжалуу ыкма болот. Андан кийин, маселе эң чоң суб-матрицаны табууга чейин азаят. 0 Бул көйгөйдү колдонуу менен чечилет динамикалык программалоо. Биз сол жана оң мамычаларды оңдоп жатабыз. Андан кийин ар бир катардын элементтеринин суммасын биринчи тилкеден экинчи тилке чейин убактылуу массивде сактаңыз. Андан кийин картаны түзөбүз, анда ушул убактылуу массивди аралап өтүп, элементтердин суммасына туура келген катар номерлерин сактайбыз. Ошентип, эгерде биз дагы бир жолу ушундай масштабдуу мааниде убактылуу массивибизде кездешсек. Эгерде ушул учурдагы катардын суммалык маанисине каршы картада сакталган катардагы элементтерди карасак, анда 0 суммасы болот деп ишенебиз. Ал эми 0 ден -1 ге өзгөрткөндө, биз эң чоң аянттан тик бурчтуу под тилкесине өткөнбүз. табууга 1 жана 0 көйгөйлөрүнүн саны бирдей болгон матрица суммасы бар эң чоң суб-матрица эми биз муну менен бүттүк.

Эң чоң аянтты 1 жана 0 сандарына барабар болгон тик бурчтуу суб-матрица табуу үчүн код

C ++ коду

#include<bits/stdc++.h>
using namespace std;

int largestAreaRectangularSubMatrixWithEqualNumberOf1sAnd0s (vector<vector<int>> matrix, int n, int m){
  
    // stores the prefixSum of rows
    vector<vector<int>> prefixSum(n,vector<int>(m));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
            prefixSum[i][j] = matrix[i][j];
    }
    
    // calculation prefix sum for each row
    for(int i=0;i<n;i++){
        for(int j=1;j<m;j++)
            prefixSum[i][j] += prefixSum[i][j-1];
    }
    
    // store indices of submatrix with maximum sum
    int startCol = 0, endCol = 0, startRow = 0, endRow = 0;
    int maxSize = 0;
    // use a map to first store the row for sum if it was not present earlier
    // else we calculate the result regarding the particular sum
    for(int firstCol=0;firstCol<m;firstCol++){
        for(int secondCol=firstCol;secondCol<m;secondCol++){
            int tmp[n]; // stores the sum between two columns for each row
            for(int row=0;row<n;row++)
                tmp[row] = prefixSum[row][secondCol] - (firstCol>0 ? prefixSum[row][firstCol-1] : 0);
            int curSum = 0;
            unordered_map<int,int> rowSumMap;
            rowSumMap[0] = -1;
            for(int curRow=0;curRow<n;curRow++){
                curSum += tmp[curRow];
                if(rowSumMap.count(curSum)) {
                    int subMatrixSize = (secondCol - firstCol + 1)*(curRow - rowSumMap[curSum]);
                    if(subMatrixSize > maxSize){
                        maxSize = subMatrixSize;
                        startCol = firstCol;
                        endCol = secondCol;
                        startRow = rowSumMap[curSum] + 1;
                        endRow = curRow;
                    }
                } else {
                    rowSumMap[curSum] = curRow;
                }
            }
        }
    }
    
    if(maxSize == 0){
        cout<<"There exists no sub-matrix with equal numbers of 0s and 1s"<<endl;
        return 0;
    }
    cout<<"Largest Sub-matrix with equal number of 1s and 0s"<<endl;
    for(int i=startRow;i<=endRow;i++){
        for(int j=startCol;j<=endCol;j++){
            cout<<(matrix[i][j]>0 ? 1 :  0)<<" ";
        }
        cout<<endl;
    }
    return maxSize;
}

int main(){
  
    int t;cin>>t;
    while(t--){
        int n,m;cin>>n>>m;
        vector<vector<int>> matrix(n,vector<int>(m));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cin>>matrix[i][j];
                matrix[i][j] = matrix[i][j] ? 1 : -1;
            }
        }
        int ans = largestAreaRectangularSubMatrixWithEqualNumberOf1sAnd0s(matrix, n, m);
        if(ans != 0)
        cout<<ans<<endl;
    }
}
1
4 4
1 1 1 1
0 1 0 1
1 0 1 0 
1 0 0 0
Largest Sub-matrix with equal number of 1s and 0s
1 1 1
1 0 1
0 1 0
0 0 0
12

Java Code

import java.util.*;
import java.lang.*;
import java.io.*;
class Main {
    static int largestAreaRectangularSubMatrixWithEqualNumberOf1sAnd0s (int[][] matrix, int n, int m){
        // stores the prefixSum of rows
        int[][] prefixSum = new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++)
                prefixSum[i][j] = matrix[i][j];
        }
    
        // calculation prefix sum for each row
        for(int i=0;i<n;i++){
            for(int j=1;j<m;j++)
                prefixSum[i][j] += prefixSum[i][j-1];
        }
    
        int startCol = 0, endCol = 0, startRow = 0, endRow = 0;
        int maxSize = 0;
        for(int firstCol=0;firstCol<m;firstCol++){
            for(int secondCol=firstCol;secondCol<m;secondCol++){
                int tmp[] = new int[n]; // stores the sum between two columns for each row
                for(int row=0;row<n;row++)
                    tmp[row] = prefixSum[row][secondCol] - (firstCol>0 ? prefixSum[row][firstCol-1] : 0);
                
                int curSum = 0;
                HashMap<Integer, Integer> rowSumMap = new HashMap<Integer, Integer>();
                rowSumMap.put(0,-1);
                for(int curRow=0;curRow<n;curRow++){
                    curSum += tmp[curRow];
                    if(rowSumMap.containsKey(curSum)) {
                        int subMatrixSize = (secondCol - firstCol + 1)*(curRow - rowSumMap.get(curSum));
                        if(subMatrixSize > maxSize){
                            maxSize = subMatrixSize;
                            startCol = firstCol;
                            endCol = secondCol;
                            startRow = rowSumMap.get(curSum) + 1;
                            endRow = curRow;
                        }
                    } else {
                        rowSumMap.put(curSum,curRow);
                    }
                }
            }
        }
        
        if(maxSize == 0){
            System.out.println("There exists no sub-matrix with equal number of 1s and 0s");
            return 0;
        }
        System.out.println("Largest Rectangular Sub-matrix with equal number of 1s and 0s");
        for(int i=startRow;i<=endRow;i++){
            for(int j=startCol;j<=endCol;j++){
                System.out.print((matrix[i][j]>0) ? "1 " : "0 ");
            }
            System.out.println();
        }
        return maxSize;
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-- > 0){
            int n = sc.nextInt();
            int m = sc.nextInt();
            int matrix[][] = new int[n][m];
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    matrix[i][j] = sc.nextInt();
                    matrix[i][j] = matrix[i][j]>0 ? 1 : -1;
                }
            }
            int ans = largestAreaRectangularSubMatrixWithEqualNumberOf1sAnd0s (matrix, n, m);
            if(ans != 0)
            System.out.println(ans);
        }
    }
}
1
4 4
1 1 1 1
0 1 0 1
1 0 1 0
1 0 0 0
Largest Rectangular Sub-matrix with equal number of 1s and 0s
1 1 1
1 0 1
0 1 0
0 0 0
12

Комплекстик анализ

Убакыт татаалдыгы: O (N ^ 3)

Бизде O (N ^ 3) полиномдук убакыт татаалдыгы бар, анткени үч уя бар циклдар. Бир цикл префикстин суммасы жана карта ыкмасы менен нөл суммасын табуу үчүн колдонулат.

Космостун татаалдыгы: O (N ^ 2)

2D префикси суммасы массивин жасагандыктан. Ошентип, 1 жана 0 көйгөйлөрүнүн саны бирдей болгон эң чоң аянттагы тик бурчтуу суб-матрица, полиномдук мейкиндиктин татаалдыгына ээ. Бизде O (N ^ 2) космостук татаалдыгы бар.