İkili Matrix Leetcode həllində xüsusi mövqelər

Çətinlik səviyyəsi Asan
Tez-tez soruşulur google
alqoritmlər Geyim kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions MatrisBaxılıb 23

Problem bəyanat

İkili Xüsusi Vəziyyətlərdə Matris problem yalnız 1s və 0s dəyərlərinin iki növünün olduğu n * m ölçülü bir matris verilmişdir. Bu hüceyrənin dəyəri 1, həmin satır və sütundakı bütün hüceyrələrdə dəyərlər 0 olduqda, hüceyrə mövqeyi xüsusi adlanır. Matrisdə nə qədər xüsusi mövqenin olduğunu qaytarmalıyıq.

misal

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

İzahat: (1,2) xüsusi bir mövqedir, çünki mat [1] [2] == 1 və 1-ci sıra və sütun 2-dəki bütün elementlər 0-dır.

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

İzahat: (0,0), (1,1) və (2,2) xüsusi mövqelərdir.

Brute Force yanaşması

Yuxarıdakı problemi həll etmək üçün kobud güc həlli tətbiq edə bilərik. yəni hər bir hüceyrəyə (i, j) gedə bilərik və dəyəri 1-dirsə, bu hüceyrənin xüsusi olma şansı var. Beləliklə, bu xüsusi hüceyrə (i, j) üçün (i) və col (j) cərgələrini tamamilə keçib həmin sətirdə və sütunda neçə ədəd olduğunu hesablayacağıq. Bu sətirdə yalnız bir 1s və bu sütunda yalnız 1s varsa, bu xana xüsusi xana sayılır. 1 * 4 matris nümunəsi:

İkili Matrix Leetcode həllində xüsusi mövqelərPin

Alqoritm

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.

İkili Matrix Leetcode həllində xüsusi mövqelər üçün tətbiqetmə

C ++ Proqramı

#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 Proqramı

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

İkili Matrix Leetcode həllində xüsusi mövqelər üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (n * m * (n + m)): Ən pis vəziyyətdə, matrisdəki hər bir hüceyrə üçün bir sətir və bir sütun, yəni O (n + m) keçirik. Beləliklə, zamanın mürəkkəbliyi O (n * m * (n + m)) olacaqdır.

Kosmik Mürəkkəblik 

O (1): Burada əlavə yaddaşdan istifadə etmirik.

Optimallaşdırılmış yanaşma

Hər bir hüceyrə üçün xətti işi sabit bir müddətə qədər azaldaraq əvvəlcədən işləyərək yuxarıdakı yanaşmanı optimallaşdırırıq.
Nə edə bilərik, əvvəlcə hər sətir və hər sütun üçün 1s sayını iki xətti massivdə saxlaya bilərik. Sonra hər bir hüceyrədən keçib dəyərinin 1 olub olmadığını yoxlayırıq, sonra bu sətirdə 1s sayının olub olmadığını və bu sütunun birinə bərabər olub olmadığını və ya sayma massivlərindən istifadə etmədiyimizi yoxlayırıq. Müəyyən bir sıra və sütun üçün bu yoxlamanı, indi davamlı bir zamanda edə bilərik. Bəzi əlavə yaddaş istifadə etməyin faydası budur, zamanın mürəkkəbliyini azalda bilər. 4 * 4 matrisinin bir nümunəsi aşağıdakı əncirdə göstərilir:

İkili Matrix Leetcode həllində xüsusi mövqelərPin

Alqoritm:

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.

İkili Matrix Leetcode həllində xüsusi mövqelər üçün tətbiqetmə

C ++ Proqramı

#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 Proqramı

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

İkili Matrix Leetcode həllində xüsusi mövqelər üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (n * m): Burada 1 sayını tapmaq üçün iki iç içə döngə işlədirik. yəni O (2 * n * m). Sonra matrisin O (n * m) alan hər hücrəsini keçdik. Buna görə ümumi zaman mürəkkəbliyi O (n * m) olacaqdır.

Kosmik Mürəkkəblik 

O (n + m): N və m ölçülü iki xətti massivdən istifadə etdik. Bu səbəbdən kosmik mürəkkəblik O (n + m) olacaqdır.

Şərh yaz

Translate »