სპეციალური პოზიციები ორობითი მატრიცის Leetcode გადაწყვეტაში


Რთული ტური Easy
ხშირად ეკითხებიან Google
Array Matrix

პრობლემის განცხადება

ორობითი განყოფილების სპეციალურ პოზიციებზე Matrix პრობლემა მოცემულია n * m ზომის მატრიცა, რომელშიც მხოლოდ ორი ტიპის მნიშვნელობებია 1s და 0s. უჯრედის პოზიციას ეწოდება სპეციალური, თუ ამ უჯრედის მნიშვნელობა არის 1, ხოლო მნიშვნელობები ამ კონკრეტულ მწკრივსა და სვეტში არსებულ ყველა უჯრედში არის 0. ჩვენ უნდა დავაბრუნოთ რამდენი სპეციალური პოზიციაა მატრიცაში.

მაგალითი

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

განმარტება: (1,2) არის განსაკუთრებული პოზიცია, რადგან mat [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

ჯავა პროგრამა

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)).

სივრცის სირთულე 

O (1): აქ დამატებით მეხსიერებას არ ვიყენებთ.

ოპტიმიზირებული მიდგომა

ზემოაღნიშნული მიდგომის ოპტიმიზაცია შეგვიძლია თითოეული უჯრედისთვის წრფივი მუშაობის მუდმივ დროზე შემცირებით წინასწარი დამუშავების გაკეთებით.
რა შეგვიძლია გავაკეთოთ, თავდაპირველად შეგვიძლია თითოეული მწკრივისა და თითოეული სვეტის 1-იანი წილის შენახვა ორ სწორ სტრიქონში. შემდეგ თითოეულ უჯრაზე გადავდივართ და ვამოწმებთ არის თუ არა მისი ღირებულება 1, შემდეგ ვამოწმებთ, არის თუ არა ამ მწკრივში 1s და ეს სვეტი ასევე ტოლია ერთი ან არ იყენებს თვლას მასივებს. კონკრეტული სტრიქონისა და სვეტის შემოწმება, ახლა შეგვიძლია გავაკეთოთ მუდმივ დროში. ეს არის დამატებითი მეხსიერების გამოყენების სარგებელი, მას შეუძლია შეამციროს დროის სირთულე. 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

ჯავა პროგრამა

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 + მ): ჩვენ გამოვიყენეთ n და m ზომის ორი წრფივი მასივი. ამიტომ სივრცის სირთულე იქნება O (n + m).