1 සහ 0 ට සමාන සංඛ්‍යාවක් ඇති විශාලතම ප්‍රදේශ හතරැස් උප අනුකෘතිය


දුෂ්කරතා මට්ටම Hard
නිතර අසනු ලැබේ ඇක්සෙන්චර් ඇත්ත වශයෙන්ම තොරතුරු එජ් මොනෝටයිප් විසඳුම් පේපෑල් Pinterest Synopsys ටයිම්ස් අන්තර්ජාලය UHG ඔප්ටම්
අරා ගතික වැඩසටහන්කරණය නියමයන්

ගැටළු ප්රකාශය

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 සමාන සංඛ්‍යාවක් ඇති බැවින් ආරම්භක න්‍යාසය අපගේ පිළිතුර වනු ඇත. මෙහි තත්වය එයයි.

ප්රවේශය

බොළඳ ප්‍රවේශය

අපට කළ හැකි පහසුම දෙය නම්, උප-අනුකෘතියේ දර්ශක හතර සඳහාම කරුණු හතරක් බැගින් සලකා බැලීමයි. අපි උප අනුකෘතිය සවි කළ විට, අපට 0s සහ 1s ගණන ගණන් කළ හැකිය. නමුත් මෙය කාර්යක්ෂම ප්‍රවේශයක් නොවන අතර නිසැකවම කාල සීමාවන් ඉක්මවා යනු ඇත. අපි සෑම 0 ක්ම -1 සමඟ වෙනස් කළහොත් අපට ගැටලුව ටිකක් ප්‍රශස්ත කළ හැකිය. පසුව, 2D උපසර්ග එකතුව තාක්‍ෂණය භාවිතා කරමින් උප අනුකෘතියේ එකතුව අපට හමු වේ. නමුත් එය භාවිතා කිරීම ප්‍රමාණවත් නොවේ.

කාර්යක්ෂම ප්‍රවේශය

කාර්යක්ෂම ප්‍රවේශයක් වනුයේ පළමුව අනුකෘතියේ සෑම 0 ක්ම negative ණ 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) හි අවකාශ සංකීර්ණතාවයක් ඇත.