በሁለትዮሽ ማትሪክስ ሌትኮድ መፍትሄ ውስጥ ልዩ የሥራ መደቦች


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ google
ሰልፍ ማትሪክስ

የችግሩ መግለጫ

በሁለትዮሽ ውስጥ በልዩ የሥራ መደቦች ውስጥ ማትሪክስ ችግር ሁለት እና ሁለት እሴቶች 1 እና 0 ብቻ ያሉበት የመጠን n * m ማትሪክስ ተሰጥቷል ፡፡ የዚያ ሕዋስ ዋጋ 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) እና ኮል (ጄ) ን ሙሉ በሙሉ እናቋርጣለን እና በዚያ ረድፍ እና በዚያ አምድ ውስጥ ስንት ቶች እንዳሉ እንቆጥራለን ፡፡ በዚህ ረድፍ ውስጥ አንድ 1 ዎቹ ብቻ እንዲሁም በዚህ አምድ ውስጥ አንድ 1 ቶች ብቻ ካሉ ይህ ሴል እንደ ልዩ ሴል ይቆጠራል ፡፡ የ 1 * 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

በሁለትዮሽ ማትሪክስ ሌትኮድ መፍትሄ ውስጥ ለተለዩ የሥራ መደቦች ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (n * m * (n + m)): በጣም በከፋ ሁኔታ ውስጥ በማትሪክስ ውስጥ ለእያንዳንዱ ሕዋስ አንድ ረድፍ እና አምድ ማለትም O (n + m) እያለፍን ነው ፡፡ ስለዚህ የጊዜ ውስብስብነት O (n * m * (n + m)) ይሆናል።

የቦታ ውስብስብነት 

ኦ (1) እዚህ ምንም ተጨማሪ ማህደረ ትውስታን እየተጠቀምን አይደለም ፡፡

የተመቻቸ አቀራረብ

የተወሰነ ቅድመ ዝግጅት በማካሄድ ለእያንዳንዱ ሴል መስመራዊ ሥራን ወደ ቋሚ ጊዜ በመቀነስ ከላይ ያለውን አካሄድ ማመቻቸት እንችላለን ፡፡
እኛ ምን ማድረግ እንችላለን ፣ በመጀመሪያ ለእያንዳንዱ ረድፍ የ 1 ቱን ቆጠራ እና እያንዳንዱን አምድ በሁለት መስመራዊ ድርድር ውስጥ ማከማቸት እንችላለን ፡፡ ከዚያ እያንዳንዱን ሴል እናቋርጣለን እና እሴቱ 1 ከሆነ እናረጋግጣለን ፣ ከዚያ በዚህ ረድፍ ውስጥ 1 ቶች መቁጠር እና እንዲሁም ይህ አምድ ከአንድ ጋር እኩል ነው ወይም ደግሞ የቁጥር አሰራሮችን አይጠቀምም ፡፡ ለተለየ ረድፍ እና አምድ ይህ መፈተሽ አሁን በቋሚ ሰዓት ማድረግ እንችላለን ፡፡ የተወሰነ ተጨማሪ ማህደረ ትውስታን የመጠቀም ጥቅም ያ ነው ፣ የጊዜ ውስብስብነትን ሊቀንስ ይችላል። የ 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

በሁለትዮሽ ማትሪክስ ሌትኮድ መፍትሄ ውስጥ ለተለዩ የሥራ መደቦች ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (n * m): እዚህ የ 1 ዎችን ቁጥር ለማግኘት ሁለት የጎጆ ቀለበቶችን እናካሂዳለን ፡፡ ማለትም O (2 * n * m) ፡፡ ከዚያ O (n * m) የሚወስደውን እያንዳንዱን የማትሪክስ ሕዋስ ተሻግረናል ፡፡ ስለዚህ አጠቃላይ የጊዜ ውስብስብነት O (n * m) ይሆናል።

የቦታ ውስብስብነት 

ኦ (n + m) የመጠን n እና ሜትር ሁለት መስመራዊ ድርድሮችን ተጠቅመናል ፡፡ ስለዚህ የቦታ ውስብስብነት O (n + m) ይሆናል።