1 və 0 bərabər sayda olan ən böyük sahə düzbucaqlı alt matris

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Accenture Həqiqətən Məlumat kənarı Monotip həllər PayPal Pinterest Sinopsis Times İnternet UHG Optum
Geyim Dinamik proqramlaşdırma MatrisBaxılıb 29

Problem bəyanat

Nx m ölçülü ikili matris verilmişdir. Məsələ 1 və 0 bərabər sayda ən böyük sahəni düzbucaqlı alt matrisin tapılmasıdır.

misal

Pin

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

İzahat: (0,1), (0,3), (3,1) və (3,3) küncləri olan submatriksi nəzərə alsaq. Bu alt matris, bərabər sayda 0s və 1s olan ən böyük düzbucaqlı submatix edir.

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

İzahat: Başlanğıc matrisin bərabər sayı 0 və 1 olduğu üçün ilk matris cavabımız olacaq. Burada belədir.

Yanaşma

Sadəlövh yanaşma

Edə biləcəyimiz ən asan şey, hər dörd istiqamətdə alt matrisin indeksləri üçün hər birinə dörd nöqtəni nəzərdən keçirməkdir. Alt matrisi düzəltdikdə 0 və 1 saylarını saya bilərik. Ancaq bu, səmərəli bir yanaşma deyil və şübhəsiz ki, vaxt məhdudiyyətlərini keçəcəkdir. Hər 0-ı -1 ilə dəyişdirsək problemi bir az optimallaşdırmaq olar. Daha sonra, 2D prefiks cəm texnikasından istifadə edərək alt matrisin cəmini tapırıq. Ancaq istifadə etməyiniz kifayət deyil.

Səmərəli yanaşma

Effektiv bir yanaşma əvvəlcə matrisdəki hər 0-nı mənfi 1 ilə dəyişdirmək olacaqdır. Bundan sonra problem 0 cəminə sahib olan ən böyük alt matrisin tapılmasına qədər azalacaq. Bu problemi artıq həll etdik. Bu problem istifadə edilərək həll edilir dinamik proqramlaşdırma. Sol və sağ sütunları düzəldirik. Sonra hər sətrin elementlərinin cəmini birinci sütundan ikinci sütuna qədər müvəqqəti massivdə saxlayın. Sonra bu müvəqqəti massivi gəzərkən elementlərin cəminə uyğun satır nömrələrini saxladığımız bir xəritə düzəldirik. Beləliklə, müvəqqəti massivimizdə yenidən eyni cəm dəyərinə rast gəlsək. Əminik ki, cari cərgədəki cəmi dəyərinə qarşı bir xəritədə saxlanılan sətirdəki elementləri 0-a bərabər olacaqdır. 0-ı -1-ə dəyişdirəndə ən böyük sahədən düzbucaqlı alt hissəyə çevrilmişdik. - 1-lə bərabər sayda matris və 0-un tapılması problemi cəmi 0 olan ən böyük alt matris və indi bununla bitmişik.

1 və 0 bərabər sayda ən böyük sahəni düzbucaqlı alt matris tapmaq üçün kod verin

C ++ kodu

#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 kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi: O (N ^ 3)

Üç iç içə olduğu üçün O (N ^ 3) polinom-zaman mürəkkəbliyinə sahibik loops. Bir döngü, prefiks Sum və xəritə texnikasından istifadə edərək sıfır cəmi tapmaq üçün istifadə olunur.

Kosmik Mürəkkəblik: O (N ^ 2)

2D prefiksi Sum serialı hazırladığımız üçün. Beləliklə, bərabər sayları 1 və 0 olan ən böyük sahə düzbucaqlı alt matris polinom boşluğu mürəkkəbliyinə malikdir. O (N ^ 2) kosmik mürəkkəbliyimiz var.

Translate »