เมทริกซ์ย่อยรูปสี่เหลี่ยมผืนผ้าที่ใหญ่ที่สุดที่มีจำนวนเท่ากับ 1 และ 0  


ระดับความยาก ยาก
ถามบ่อยใน แอคเซนเจอร์ จริง ขอบข้อมูล โซลูชั่นโมโนไทป์ บัตรเครดิต/เดบิต หรือ PayPal Pinterest Synopsys ไทม์อินเทอร์เน็ต 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

คำอธิบาย: ถ้าเราพิจารณา subatrix ด้วยมุม (0,1), (0,3), (3,1) และ (3,3) เมทริกซ์ย่อยนี้ทำให้เมทริกซ์ย่อยรูปสี่เหลี่ยมผืนผ้าที่ใหญ่ที่สุดมีจำนวน 0 และ 1 เท่ากัน

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

คำอธิบาย: เนื่องจากเมทริกซ์เริ่มต้นมีจำนวน 0 และ 1 เท่ากันดังนั้นเมทริกซ์เริ่มต้นจึงเป็นคำตอบของเรา นั่นคือกรณีที่นี่

เข้าใกล้  

แนวทางที่ไร้เดียงสา

สิ่งที่ง่ายที่สุดที่เราสามารถทำได้คือการพิจารณาสี่พอยน์เตอร์สำหรับดัชนีย่อยของเมทริกซ์ทั้งสี่ทิศทาง เมื่อเราแก้ไขเมทริกซ์ย่อยเราสามารถนับจำนวน 0s และ 1s ได้ แต่นี่ไม่ใช่แนวทางที่มีประสิทธิภาพและจะเกินเวลาที่ จำกัด อย่างแน่นอน เราสามารถเพิ่มประสิทธิภาพของปัญหาได้เล็กน้อยถ้าเราเปลี่ยน 0 แต่ละตัวด้วย -1 หลังจากนั้นเราจะหาผลรวมของเมทริกซ์ย่อยโดยใช้เทคนิคผลรวมคำนำหน้า 2 มิติ แต่ถึงแม้ว่าการใช้แค่นั้นจะไม่เพียงพอ

แนวทางที่มีประสิทธิภาพ

แนวทางที่มีประสิทธิภาพจะต้องเปลี่ยน 0 แต่ละ 1 ในเมทริกซ์ด้วยค่าลบ 0 หลังจากนั้นปัญหาจะลดลงเป็นการค้นหาเมทริกซ์ย่อยที่ใหญ่ที่สุดที่มีผลรวม XNUMX เราได้กล่าวถึงปัญหานี้แล้ว ปัญหานี้แก้ไขได้โดยใช้ การเขียนโปรแกรมแบบไดนามิก. เราแก้ไขคอลัมน์ซ้ายและขวา จากนั้นเก็บผลรวมของแต่ละแถวจากคอลัมน์แรกไปยังคอลัมน์ที่สองในอาร์เรย์ชั่วคราว จากนั้นเราสร้างแผนที่ซึ่งเราจัดเก็บหมายเลขแถวที่สอดคล้องกับผลรวมขององค์ประกอบในขณะที่ข้ามอาร์เรย์ชั่วคราวนี้ ดังนั้นหากเราพบค่าผลรวมเดียวกันอีกครั้งในอาร์เรย์ชั่วคราวของเรา เราแน่ใจว่าถ้าเราพิจารณาองค์ประกอบจากแถวซึ่งปัจจุบันถูกเก็บไว้ในแผนที่เทียบกับค่าผลรวมของแถวปัจจุบันนี้จะมีผลรวม 0 และเมื่อเราเปลี่ยน 0 เป็น -1 เราได้แปลงจากพื้นที่ย่อยสี่เหลี่ยมที่ใหญ่ที่สุด เมทริกซ์ที่มีจำนวนเท่ากับ 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) เนื่องจากมีสามตัวที่ซ้อนกัน ลูป. หนึ่งวงใช้สำหรับการค้นหาผลรวมศูนย์โดยใช้คำนำหน้าผลรวมและเทคนิคแผนที่

ดูสิ่งนี้ด้วย
ตรวจสอบการสร้างอาร์เรย์ผ่านโซลูชัน Leetcode ที่เชื่อมต่อกัน

ความซับซ้อนของอวกาศ: O (N ^ 2)

เนื่องจากเราสร้างอาร์เรย์ Sum คำนำหน้าแบบ 2D ดังนั้นเมทริกซ์ย่อยรูปสี่เหลี่ยมผืนผ้าที่มีพื้นที่ใหญ่ที่สุดที่มีจำนวนเท่ากับ 1 และปัญหา 0 จึงมีความซับซ้อนของปริภูมิพหุนาม เรามีความซับซ้อนของพื้นที่ของ O (N ^ 2)