ყველაზე დიდი ფართობის მართკუთხა ქვე-მატრიცა თანაბარი რაოდენობით 1-ით და 0-ით


Რთული ტური Hard
ხშირად ეკითხებიან Accenture ნამდვილად ინფო ზღვარი მონოტიპის გადაწყვეტილებები PayPal Pinterest ანოტაცია Times ინტერნეტი UHG Optum
Array დინამიური პროგრამირება 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

განმარტება: ვინაიდან საწყის მატრიცას ჰქონდა 0 და 1 თანაბარი რიცხვი, მაშინ საწყისი პასუხი იქნება ჩვენი პასუხი. აქ ასეა საქმე.

მიდგომა

გულუბრყვილო მიდგომა

უმარტივესი რისი გაკეთება შეგვიძლია, არის ოთხი წერტილის გათვალისწინება ქვე-მატრიცის ინდექსებისთვის ოთხივე მიმართულებით. როდესაც დავაფიქსირეთ ქვე-მატრიცა, შეგვიძლია დავთვალოთ 0-სა და 1-ის რიცხვი. მაგრამ ეს არ არის ეფექტური მიდგომა და ნამდვილად გადააჭარბებს დროის შეზღუდვებს. პრობლემის ოპტიმიზაცია შეგვიძლია, თუ თითოეულ 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

ჯავის კოდი

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), რადგან ისინი სამია ჩასმული loops. ერთი მარყუჟი გამოიყენება ნულოვანი ჯამის მოსაძებნად პრეფიქსი Sum და რუკის ტექნიკის გამოყენებით.

სივრცის სირთულე: O (N ^ 2)

მას შემდეგ, რაც ჩვენ შევქმენით 2D პრეფიქსი Sum მასივი. ამრიგად, ყველაზე დიდი ფართობის მართკუთხა ქვე-მატრიცა, თანაბარი 1 – ისა და 0 – ის პრობლემით, მრავალწევრის სივრცის სირთულეს წარმოადგენს. ჩვენ გვაქვს O (N ^ 2) სირთულის სივრცე.