ตำแหน่งพิเศษในโซลูชัน Leetcode เมทริกซ์แบบไบนารี


ระดับความยาก สะดวกสบาย
ถามบ่อยใน Google
แถว มดลูก

คำชี้แจงปัญหา

ในตำแหน่งพิเศษในไบนารี มดลูก ปัญหาเมทริกซ์ของขนาด n * m จะได้รับซึ่งมีเพียงสองประเภทของค่า 1s และ 0s ตำแหน่งเซลล์เรียกว่าพิเศษถ้าค่าของเซลล์นั้นเป็น 1 และค่าในเซลล์ทั้งหมดในแถวและคอลัมน์นั้นเป็น 0 เราต้องส่งคืนจำนวนตำแหน่งพิเศษในเมทริกซ์

ตัวอย่าง

mat = [[1,0,0],
       [0,0,1],
       [1,0,0]]
1

คำอธิบาย: (1,2) เป็นตำแหน่งพิเศษเนื่องจาก mat [1] [2] == 1 และองค์ประกอบอื่น ๆ ทั้งหมดในแถว 1 และคอลัมน์ 2 เป็น 0

mat = [[1,0,0],
       [0,1,0],
       [0,0,1]]
3

คำอธิบาย: (0,0), (1,1) และ (2,2) เป็นตำแหน่งพิเศษ

แนวทาง Brute Force

ในการแก้ปัญหาข้างต้นเราสามารถใช้วิธีแก้ปัญหา brute force กล่าวคือเราสามารถไปที่แต่ละเซลล์ (i, j) และถ้าค่าของมันเป็น 1 ก็มีโอกาสที่เซลล์นี้จะพิเศษ ดังนั้นสำหรับเซลล์นี้ (i, j) เราจะข้ามแถว (i) และ col (j) ทั้งหมดและนับจำนวน 1 ในแถวนั้นและคอลัมน์นั้น หากแถวนี้มีเพียง 1s เดียวและ 1 ในคอลัมน์นี้เท่านั้นเซลล์นี้จะถูกนับเป็นเซลล์พิเศษ ตัวอย่างเมทริกซ์ 4 * 4:

ตำแหน่งพิเศษในโซลูชัน Leetcode เมทริกซ์แบบไบนารี

ขั้นตอนวิธี

Create a variable special to count the special positions.
Traverse the matrix using nested loop for cell(i,j).
If value of current cell(i,j) is 1, then:
    Traverse the row(i) and find the count of 1s in that row.
    Traverse the col(j) and find the count of 1s in that column.
    if count of 1s in row(i) is 1 and count of 1s in col(j) is also 1, then:
        Increment the count of special position.
Return the value of variable special.

การนำไปใช้งานสำหรับตำแหน่งพิเศษในโซลูชัน Leetcode แบบไบนารีเมทริกซ์

โปรแกรม C ++

#include <bits/stdc++.h>
using namespace std;

int numSpecial(vector<vector<int>>& mat) 
{
    int n=mat.size();
    int m=mat[0].size();

    int special=0;

    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    if(mat[i][j])
    {
        int col=0,row=0;
        for(int k=0;k<n;k++) col+= mat[k][j];
        for(int k=0;k<m;k++) row+= mat[i][k];

        if(col==1 && row==1) special++;

    }

    return special;
}

int main() 
{
    vector<vector<int> > mat={
        {0,0,0,1},
        {1,0,0,0},
        {0,1,1,0},
        {0,0,0,0}
    };
    
    cout<<numSpecial(mat)<<endl;

  return 0; 
}
2

โปรแกรม Java

import java.lang.*;

class Rextester
{  
    public static int numSpecial(int[][] mat) 
    {
        int n=mat.length;
        int m=mat[0].length;

        int special=0;

        for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        if(mat[i][j]==1)
        {
            int col=0,row=0;
            for(int k=0;k<n;k++) col+= mat[k][j];
            for(int k=0;k<m;k++) row+= mat[i][k];

            if(col==1 && row==1) special++;
        }

        return special;
    }
    
    public static void main(String args[])
    {
        int[][] mat={
            {0,0,0,1},
            {1,0,0,0},
            {0,1,1,0},
            {0,0,0,0}
         };

        System.out.println(numSpecial(mat));
        
    }
}
2

การวิเคราะห์ความซับซ้อนสำหรับตำแหน่งพิเศษในโซลูชัน Leetcode แบบไบนารีเมทริกซ์

ความซับซ้อนของเวลา

O (n * m * (n + m)): ในกรณีที่เลวร้ายที่สุดเรากำลังข้ามแถวและคอลัมน์เช่น O (n + m) สำหรับแต่ละเซลล์ในเมทริกซ์ ดังนั้นความซับซ้อนของเวลาจะเป็น O (n * m * (n + m))

ความซับซ้อนของอวกาศ 

O (1): เราไม่ได้ใช้หน่วยความจำเพิ่มเติมใด ๆ ที่นี่

แนวทางที่ดีที่สุด

เราสามารถปรับแนวทางข้างต้นให้เหมาะสมโดยการลดงานเชิงเส้นสำหรับแต่ละเซลล์ให้เป็นเวลาคงที่โดยการประมวลผลล่วงหน้าบางส่วน
สิ่งที่เราทำได้คือเริ่มแรกเราสามารถจัดเก็บจำนวน 1 วินาทีสำหรับแต่ละแถวและแต่ละคอลัมน์ในอาร์เรย์เชิงเส้นสองชุด จากนั้นเราสำรวจแต่ละเซลล์และตรวจสอบว่าค่าของมันคือ 1 หรือไม่จากนั้นเราจะตรวจสอบว่าจำนวน 1 ในแถวนี้และคอลัมน์นี้เท่ากับหนึ่งหรือไม่ใช้อาร์เรย์นับ การตรวจสอบแถวและคอลัมน์เฉพาะนี้เราสามารถทำได้ในเวลาคงที่ นั่นเป็นประโยชน์ของการใช้หน่วยความจำเพิ่มเติมซึ่งสามารถลดความซับซ้อนของเวลาได้ ตัวอย่างของเมทริกซ์ 4 * 4 แสดงในรูปด้านล่าง:

ตำแหน่งพิเศษในโซลูชัน Leetcode เมทริกซ์แบบไบนารี

อัลกอริทึม:

Create a variable special to count the special positions.
Create two arrays rows and cols of size n and m respectively.
Traverse each row(i) and count the numbers of 1s for each row and store it in rows[i].
Traverse each col(i) and count the numbers of 1s for each column and store it in cols[i].
Traverse the matrix using nested loop for cell (i,j).
    If value of current cell(i,j) is 1 and rows[i]==1 and cols[j]==1, then:
        Increment the count of special position.
Return the value of variable special.

การนำไปใช้งานสำหรับตำแหน่งพิเศษในโซลูชัน Leetcode แบบไบนารีเมทริกซ์

โปรแกรม C ++

#include <bits/stdc++.h>
using namespace std;

int numSpecial(vector<vector<int>>& mat) 
{
    int n=mat.size();
    int m=mat[0].size();

    int special=0;

    int* rows= new int[n];
    int* cols= new int[m];

    for(int i=0;i<n;i++)
    {
        int cnt=0;
        for(int j=0;j<m;j++)  cnt+=mat[i][j];
        rows[i]=cnt;
    }

    for(int j=0;j<m;j++)
    {
        int cnt=0;
        for(int i=0;i<n;i++)  cnt+=mat[i][j];
        cols[j]=cnt;
    }

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if( mat[i][j]==1 && rows[i]==1 && cols[j]==1 )  special++;

    return special;
}

int main() 
{
    vector<vector<int> > mat={
        {0,0,0,1},
        {1,0,0,0},
        {0,1,1,0},
        {0,0,0,0}
    };
    
    cout<<numSpecial(mat)<<endl;

  return 0; 
}
2

โปรแกรม Java

import java.lang.*;

class Rextester
{  
    public static int numSpecial(int[][] mat) 
    {
        int n=mat.length;
        int m=mat[0].length;
        
        int special=0;
        
        int[] rows= new int[n];
        int[] cols= new int[m];
        
        for(int i=0;i<n;i++)
        {
            int cnt=0;
            for(int j=0;j<m;j++)  cnt+=mat[i][j];
            rows[i]=cnt;
        }
        
        for(int j=0;j<m;j++)
        {
            int cnt=0;
            for(int i=0;i<n;i++) cnt+=mat[i][j];
            cols[j]=cnt;
        }
        
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if( mat[i][j]==1 && rows[i]==1 && cols[j]==1 )  special++;
        
        return special;
    }
    
    public static void main(String args[])
    {
        int[][] mat={
            {0,0,0,1},
            {1,0,0,0},
            {0,1,1,0},
            {0,0,0,0}
         };

        System.out.println(numSpecial(mat));
        
    }
}
2

การวิเคราะห์ความซับซ้อนสำหรับตำแหน่งพิเศษในโซลูชัน Leetcode แบบไบนารีเมทริกซ์

ความซับซ้อนของเวลา

O (n * ม.): ที่นี่เรากำลังเรียกใช้สองลูปซ้อนกันเพื่อค้นหาจำนวน 1 ได้แก่ O (2 * n * m) จากนั้นเราสำรวจแต่ละเซลล์ของเมทริกซ์ซึ่งใช้เวลา O (n * m) ดังนั้นความซับซ้อนของเวลาโดยรวมจะเป็น O (n * m)

ความซับซ้อนของอวกาศ 

O (n + ม.): เราใช้อาร์เรย์เชิงเส้นสองเส้นขนาด n และ m ดังนั้นความซับซ้อนของพื้นที่จะเป็น O (n + m)