1 மற்றும் 0 இன் சம எண்ணிக்கையுடன் மிகப்பெரிய பகுதி செவ்வக துணை மேட்ரிக்ஸ்


சிரமம் நிலை கடின
அடிக்கடி கேட்கப்படுகிறது அக்சன்சர் உண்மையில் தகவல் எட்ஜ் மோனோடைப் தீர்வுகள் பேபால் இடுகைகள் சினாப்சிஸ் டைம்ஸ் இணையம் யுஎச்ஜி ஆப்டம்
அணி டைனமிக் புரோகிராமிங் மேட்ரிக்ஸ்

சிக்கல் அறிக்கை

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

விளக்கம்: ஆரம்ப மேட்ரிக்ஸில் 0 கள் மற்றும் 1 கள் சம எண்ணிக்கையைக் கொண்டிருப்பதால், ஆரம்ப அணி எங்கள் பதிலாக இருக்கும். இங்கேயும் அப்படித்தான்.

அணுகுமுறை

அப்பாவி அணுகுமுறை

நாம் செய்யக்கூடிய எளிதான விஷயம், நான்கு திசைகளிலும் துணை மேட்ரிக்ஸின் குறியீடுகளுக்கு தலா நான்கு சுட்டிகள் கருதுகின்றன. துணை மேட்ரிக்ஸை நாம் சரிசெய்யும்போது, ​​0 கள் மற்றும் 1 வி எண்ணிக்கையை எண்ணலாம். ஆனால் இது ஒரு திறமையான அணுகுமுறை அல்ல, நிச்சயமாக நேரக் கட்டுப்பாடுகளை மீறும். ஒவ்வொரு 0 ஐ -1 உடன் மாற்றினால் சிக்கலை சிறிது மேம்படுத்தலாம். பின்னர், 2D முன்னொட்டு தொகை நுட்பத்தைப் பயன்படுத்தி துணை மேட்ரிக்ஸின் தொகையைக் காணலாம். ஆனால் அதைப் பயன்படுத்துவது போதாது.

திறமையான அணுகுமுறை

மேட்ரிக்ஸில் ஒவ்வொரு 0 ஐ முதலில் எதிர்மறை 1 உடன் மாற்றுவது ஒரு திறமையான அணுகுமுறையாக இருக்கும். அதன் பிறகு, தொகை 0 ஐக் கொண்ட மிகப்பெரிய துணை மேட்ரிக்ஸைக் கண்டுபிடிப்பதில் சிக்கல் குறைகிறது. பயன்படுத்தி இந்த சிக்கல் தீர்க்கப்படுகிறது டைனமிக் நிரலாக்க. இடது மற்றும் வலது நெடுவரிசைகளை சரிசெய்கிறோம். ஒவ்வொரு வரிசையின் உறுப்புகளின் கூட்டுத்தொகையை முதல் நெடுவரிசையிலிருந்து இரண்டாவது நெடுவரிசை வரை தற்காலிக வரிசையில் சேமிக்கவும். இந்த தற்காலிக வரிசையை கடந்து செல்லும்போது உறுப்புகளின் கூட்டுத்தொகைக்கு ஒத்த வரிசை எண்களை சேமித்து வைக்கும் ஒரு வரைபடத்தை உருவாக்குகிறோம். எனவே, எங்கள் தற்காலிக வரிசையில் அதே தொகை மதிப்பை மீண்டும் சந்தித்தால். இந்த தற்போதைய வரிசையின் கூட்டு மதிப்புக்கு எதிராக ஒரு வரைபடத்தில் தற்போது சேமிக்கப்பட்டுள்ள வரிசையின் உறுப்புகளைக் கருத்தில் கொண்டால், தொகை 0 இருக்கும் என்று நாங்கள் உறுதியாக நம்புகிறோம். மேலும் 0 க்கு -1 ஆக மாற்றியபோது, ​​மிகப்பெரிய பகுதி செவ்வக துணை இருந்து மாற்றினோம் 1 மற்றும் 0 இன் சம எண்ணிக்கையுடன் மாட்ரிக்ஸ் கண்டுபிடிப்பதில் சிக்கல் தொகை 0 கொண்ட மிகப்பெரிய துணை மேட்ரிக்ஸ் இப்போது நாங்கள் அதை முடித்துவிட்டோம்.

1 மற்றும் 0 இன் சம எண்ணிக்கையுடன் மிகப்பெரிய பகுதி செவ்வக துணை மேட்ரிக்ஸைக் கண்டறியும் குறியீடு

சி ++ குறியீடு

#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

ஜாவா குறியீடு

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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது: ஓ (என் ^ 3)

O (N ^ 3) இன் பல்லுறுப்புக்கோட்டு நேர சிக்கலானது எங்களிடம் உள்ளது, ஏனெனில் மூன்று கூடுகள் உள்ளன சுழல்கள். கூட்டுத்தொகை மற்றும் வரைபட நுட்பத்தைப் பயன்படுத்தி பூஜ்ஜிய தொகையைக் கண்டறிய ஒரு வளையம் பயன்படுத்தப்படுகிறது.

விண்வெளி சிக்கலானது: ஓ (என் ^ 2)

நாங்கள் 2D முன்னொட்டு தொகை வரிசையை உருவாக்கியதால். ஆகவே, 1 மற்றும் 0 இன் சம எண்ணிக்கையுடன் கூடிய மிகப்பெரிய பகுதி செவ்வக துணை மேட்ரிக்ஸ் பல்லுறுப்புக்கோட்டு விண்வெளி சிக்கலைக் கொண்டுள்ளது. O (N ^ 2) இன் விண்வெளி சிக்கலானது எங்களிடம் உள்ளது.