תפקידים מיוחדים בפתרון Leetcode מטריצה ​​בינארית


רמת קושי קַל
נשאל לעתים קרובות Google
מערך מַטרִיצָה

הצהרת בעיה

בתפקידים מיוחדים בבינארי מַטרִיצָה בעיה ניתנת מטריצה ​​בגודל n * m שיש בה רק שני סוגים של ערכים 1s ו- 0s. מיקום תא נקרא מיוחד אם הערך של אותו תא הוא 1 והערכים בכל התאים באותה שורה ועמודה מסוימים הם 0. עלינו להחזיר כמה מיקומים מיוחדים יש במטריצה.

דוגמה

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

הסבר: (1,2) היא מיקום מיוחד מכיוון שמזרן [1] [2] == 1 וכל שאר האלמנטים בשורה 1 ועמודה 2 הם 0.

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

הסבר: (0,0), (1,1) ו- (2,2) הם עמדות מיוחדות.

גישת כוח הברוט

כדי לפתור את הבעיה הנ"ל אנו יכולים ליישם פתרון כוח אכזרי. כלומר נוכל ללכת לכל תא (i, j) ואם הערך שלו הוא 1 אז יש סיכוי שתא זה יהיה מיוחד. אז עבור תא מסוים זה (i, j) היינו חוצים את השורה (i) ו- col (j) לחלוטין ומספרים כמה 1 יש שם באותה שורה ובאותה העמודה. אם יש רק 1 אחד בשורה זו, כמו גם 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

ניתוח מורכבות לתפקידים מיוחדים בפתרון ליקוד מטריקס בינארי

מורכבות זמן

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

ניתוח מורכבות לתפקידים מיוחדים בפתרון ליקוד מטריקס בינארי

מורכבות זמן

O (n * m): כאן אנו מפעילים שני לולאות מקוננות למציאת מספר 1. כלומר O (2 * n * m). ואז עברנו כל תא של המטריצה ​​שלוקח O (n * m). לכן מורכבות הזמן הכוללת תהיה O (n * m).

מורכבות בחלל 

O (n + m): השתמשנו בשני מערכים לינאריים בגודל n ו- m. לכן מורכבות החלל תהיה O (n + m).