د بائنری میټریکس لیټکوډ حل کې ځانګړي موقعیتونه


مشکل کچه په اسانۍ سره
په مکرر ډول دننه پوښتل کیږي د ګوګل
پیشه جدول

ستونزه بیان

په بائنری کې ځانګړي موقعیتونو کې جدول ستونزه د n * m کچه میټرکس ورکړل شوی چې پکې 1s او 0s یوازې دوه ډوله ارزښتونه شتون لري. د حجری موقعیت ته ځانګړی ویل کیږي که چیرې د دې حجرې ارزښت 1 وي او پدې ځانګړي قطار او کالم کې په ټولو حجرو کې ارزښتونه 0 وي. موږ باید بیرته راستون شو چې په میټرکس کې څو ځانګړي موقعیتونه شتون لري.

بېلګه

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

توضیحي: (1,2،1) یو ځانګړی موقعیت لري ځکه چې mat [2] [1] == 1 او په قطار 2 او کالم 0 کې ټول نور عناصر XNUMX دي.

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

توضیحي: (0,0،1,1) ، (2,2،XNUMX) او (XNUMX،XNUMX) ځانګړي دریځونه دي.

د وحشي ځواک لید

د پورتنۍ ستونزې حلولو لپاره موږ کولی شو د ځنګل ځواک حل پلي کړو. د مثال په توګه موږ کولی شو هرې حجرې ته لاړ شو (i ، j) او که چیرې د دې ارزښت 1 وي نو د دې حجرې امکان شتون لري چې ځانګړي وي. نو د دې ځانګړي حجرې لپاره (i ، j) موږ به قطار (i) او col (j) په بشپړ ډول تیر کړو او حساب به یې وکړم چې پدې قطار کې څومره 1s شتون لري. که چیرې پدې قطار کې یوازې یو 1s وي او همدا رنګه پدې کالم کې یوازې 1s وي نو دا حجره د ځانګړي حجرې په توګه شمیرل کیږي. د 4 * 4 میټریک مثال:

د بائنری میټریکس لیټکوډ حل کې ځانګړي موقعیتونه

الګوریتم

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.

په بائنری میټریکس لیټکوډ حل کې د ځانګړي موقعیتونو پلي کول

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

جاوا پروګرام

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): موږ دلته اضافي حافظه نه کاروو.

غوره کړنلاره

موږ کولی شو د یو څه دمخه پروسس کولو په واسطه په دوامداره توګه د هرې حجرې لپاره د خطي کار کمولو سره پورتنۍ کړنلاره اصلاح کړو.
څه چې موږ کولی شو هغه دی ، په پیل کې موږ د هر قطار لپاره د 1s شمیره او هر کالم په دوه خطي صفونو کې ذخیره کولی شو. بیا موږ هر حجره تعقیب کوو او ګورو چې آیا د دې ارزښت 1 دی ، نو بیا موږ ګورو چې ایا پدې قطار کې د 1s شمیره شتون لري او دا کالم هم د یو سره مساوي دی یا د شمیرو تیرولو کارولو سره نه. دا د ځانګړي قطار او کالم لپاره چک کول ، موږ اوس کولی شو په دوامداره وخت کې. دا د ځینې اضافي حافظې کارولو ګټه ده ، دا کولی شي د وخت پیچلتیا کم کړي. د 4 * 4 میټریک مثال په لاندې شکل کې ښودل شوی:

د بائنری میټریکس لیټکوډ حل کې ځانګړي موقعیتونه

الګوریتم:

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.

په بائنری میټریکس لیټکوډ حل کې د ځانګړي موقعیتونو پلي کول

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

جاوا پروګرام

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 * م): دلته موږ د 1s شمیرو موندلو لپاره دوه ځليدلي لوپونه پرمخ وړو. د مثال په توګه O (2 * n * م). بیا موږ د میټریکس هر حجره تعقیب کړه کوم چې O (n * m) اخلي. نو د دې لپاره د ټول وخت پیچلتیا به O (n * m) وي.

د ځای پیچلتیا 

O (n + m): موږ د n او m کچه دوه خطي تیرونه کارولي دي. نو د ځای پیچلتیا به O (n + m) وي.