Ορθογώνιος υπο-μήτρα μεγαλύτερης περιοχής με ίσο αριθμό 1 και 0


Επίπεδο δυσκολίας Σκληρά
Συχνές ερωτήσεις Accenture Πράγματι Πληροφορίες Edge Μονοτυπικές Λύσεις PayPal Pinterest Synopsys Times Internet UHG Optum
Παράταξη Δυναμικός προγραμματισμός Μήτρα

Δήλωση προβλήματος

Δεδομένου δυαδικού πίνακα μήκους 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). Αυτή η υπο-μήτρα δημιουργεί το μεγαλύτερο ορθογώνιο υπο-μήτρα με ίσο αριθμό 0s και 1s.

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

Επεξήγηση: Δεδομένου ότι ο αρχικός πίνακας είχε ίσο αριθμό 0s και 1s, τότε η αρχική μήτρα θα είναι η απάντησή μας. Αυτό συμβαίνει εδώ.

Προσέγγιση

Naive προσέγγιση

Το ευκολότερο πράγμα που μπορούμε να κάνουμε, είναι να εξετάσουμε τέσσερις δείκτες ο καθένας για τους δείκτες του υπο-πίνακα και στις τέσσερις κατευθύνσεις. Όταν διορθώσαμε την υπο-μήτρα, μπορούμε να μετρήσουμε τον αριθμό των 0 και 1s. Αλλά αυτή δεν είναι μια αποτελεσματική προσέγγιση και σίγουρα θα ξεπεράσει τους χρονικούς περιορισμούς. Μπορούμε να βελτιστοποιήσουμε λίγο το πρόβλημα αν αλλάξουμε κάθε 0 με το -1. Στη συνέχεια, βρίσκουμε το άθροισμα της υπο-μήτρας χρησιμοποιώντας την τεχνική 2D προθέματος αθροίσματος. Αλλά παρόλο που η χρήση του δεν θα είναι αρκετή.

Αποτελεσματική προσέγγιση

Μια αποτελεσματική προσέγγιση θα ήταν να αλλάξετε πρώτα κάθε 0 στη μήτρα με αρνητικό 1. Στη συνέχεια, το πρόβλημα μειώνεται στην εύρεση του μεγαλύτερου υπο-μήτρας με άθροισμα 0. Έχουμε ήδη καλύψει αυτό το πρόβλημα. Αυτό το πρόβλημα επιλύεται χρησιμοποιώντας δυναμικό προγραμματισμό. Διορθώνουμε την αριστερή και τη δεξιά στήλη. Στη συνέχεια, αποθηκεύστε το άθροισμα των στοιχείων κάθε σειράς από την πρώτη στήλη στη δεύτερη στήλη σε έναν προσωρινό πίνακα. Στη συνέχεια, φτιάχνουμε έναν χάρτη, όπου αποθηκεύουμε αριθμούς σειρών που αντιστοιχούν στο άθροισμα των στοιχείων ενώ διασχίζουμε αυτόν τον προσωρινό πίνακα. Έτσι, εάν συναντήσουμε ξανά την ίδια τιμή αθροίσματος στον προσωρινό μας πίνακα. Είμαστε βέβαιοι ότι αν λάβουμε υπόψη τα στοιχεία από τη σειρά, τα οποία είναι αποθηκευμένα σε χάρτη έναντι της τιμής αθροίσματος σε αυτήν την τρέχουσα σειρά, θα έχουν το άθροισμα 0. Και όταν αλλάξαμε 0 σε -1, είχαμε μετατραπεί από τη μεγαλύτερη ορθογώνια περιοχή -matrix με ίσο αριθμό 1 και 0 πρόβλημα στην εύρεση η μεγαλύτερη υπο-μήτρα με άθροισμα 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

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).