Спецыяльныя пазіцыі ў двайковай матрычнай развязцы штрых-кода


Узровень складанасці Лёгка
Часта пытаюцца ў 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:

Спецыяльныя пазіцыі ў двайковай матрычнай развязцы штрых-кода

Алгарытм

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 паказаны на мал. Ніжэй:

Спецыяльныя пазіцыі ў двайковай матрычнай развязцы штрых-кода

Алгарытм:

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 (п * м): Тут мы запускаем дзве ўкладзеныя цыклы для пошуку колькасці 1. г.зн. O (2 * n * m). Потым мы прайшлі кожную ячэйку матрыцы, якая прымае O (n * m). Таму агульная складанасць часу будзе O (n * m).

Касмічная складанасць 

O (n + m): Мы выкарысталі два лінейныя масівы памерам n і m. Таму касмічная складанасць будзе O (n + m).