Мавқеъҳои махсус дар ҳалли Leetcode матрицаи дуӣ


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Google
тартиботи ҳарбӣ Matrix

Изҳороти мушкилот

Дар вазифаҳои махсус дар дуӣ Matrix масъала матритсаи андозаи 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

Таҳлили мураккабӣ барои ҷойгоҳҳои махсус дар ҳалли матритсаи дуӣ Leetcode

Мураккабии вақт

O (n * m * (n + m)): Дар бадтарин ҳолат, мо сатр ва сутунро тай карда истодаем, яъне O (n + m) барои ҳар як чашмак дар матритса. Аз ин рӯ, мураккабии вақт O (n * m * (n + m)) хоҳад буд.

Мураккабии фазо 

О (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 * m): Дар ин ҷо мо ду ҳалқаи лона барои дарёфти шумораи 1ҳоро иҷро карда истодаем. яъне O (2 * n * m). Сипас, мо ҳар як ҳуҷайраи матритсаро, ки O (n * m) мегирад, тай кардем. Аз ин рӯ, мураккабии умумии вақт O (n * m) хоҳад буд.

Мураккабии фазо 

O (n + m): Мо ду массиви хаттии андозаи n ва m -ро истифода кардем. Аз ин рӯ, мураккабии фазо O (n + m) хоҳад буд.