ಬೈನರಿ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ವಿಶೇಷ ಸ್ಥಾನಗಳು


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಗೂಗಲ್
ಅರೇ ಮ್ಯಾಟ್ರಿಕ್ಸ್

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

ಬೈನರಿನಲ್ಲಿ ವಿಶೇಷ ಸ್ಥಾನಗಳಲ್ಲಿ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಸಮಸ್ಯೆ n * m ಗಾತ್ರದ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಅನ್ನು ನೀಡಲಾಗಿದೆ, ಇದರಲ್ಲಿ 1 ಸೆ ಮತ್ತು 0 ಸೆ ಮೌಲ್ಯಗಳು ಮಾತ್ರ ಇರುತ್ತವೆ. ಆ ಕೋಶದ ಮೌಲ್ಯವು 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) ಮತ್ತು ಕೋಲ್ (j) ಗಳನ್ನು ಸಂಪೂರ್ಣವಾಗಿ ಹಾದುಹೋಗುತ್ತೇವೆ ಮತ್ತು ಆ ಸಾಲು ಮತ್ತು ಆ ಕಾಲಂನಲ್ಲಿ ಎಷ್ಟು 1 ಸೆಗಳಿವೆ ಎಂದು ಎಣಿಸುತ್ತೇವೆ. ಈ ಸಾಲಿನಲ್ಲಿ ಕೇವಲ 1 ಸೆ ಮತ್ತು ಈ ಕಾಲಂನಲ್ಲಿ ಕೇವಲ 1 ಸೆ ಇದ್ದರೆ ಈ ಕೋಶವನ್ನು ವಿಶೇಷ ಕೋಶ ಎಂದು ಪರಿಗಣಿಸಲಾಗುತ್ತದೆ. 4 * 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.

ಬೈನರಿ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ವಿಶೇಷ ಸ್ಥಾನಗಳಿಗೆ ಅನುಷ್ಠಾನ

ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#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

ಬೈನರಿ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ವಿಶೇಷ ಸ್ಥಾನಗಳಿಗಾಗಿ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

O (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.

ಬೈನರಿ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ವಿಶೇಷ ಸ್ಥಾನಗಳಿಗೆ ಅನುಷ್ಠಾನ

ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#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

ಬೈನರಿ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ವಿಶೇಷ ಸ್ಥಾನಗಳಿಗಾಗಿ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್ * ಮೀ): 1 ಸೆ ಸಂಖ್ಯೆಯನ್ನು ಕಂಡುಹಿಡಿಯಲು ಇಲ್ಲಿ ನಾವು ಎರಡು ನೆಸ್ಟೆಡ್ ಲೂಪ್ಗಳನ್ನು ಚಲಾಯಿಸುತ್ತಿದ್ದೇವೆ. ಅಂದರೆ O (2 * n * m). ನಂತರ ನಾವು O (n * m) ತೆಗೆದುಕೊಳ್ಳುವ ಮ್ಯಾಟ್ರಿಕ್ಸ್‌ನ ಪ್ರತಿಯೊಂದು ಕೋಶವನ್ನು ಹಾದುಹೋದೆವು. ಆದ್ದರಿಂದ ಒಟ್ಟಾರೆ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು O (n * m) ಆಗಿರುತ್ತದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ 

ಒ (ಎನ್ + ಮೀ): ನಾವು n ಮತ್ತು m ಗಾತ್ರದ ಎರಡು ರೇಖೀಯ ಸರಣಿಗಳನ್ನು ಬಳಸಿದ್ದೇವೆ. ಆದ್ದರಿಂದ ಸ್ಥಳ ಸಂಕೀರ್ಣತೆಯು O (n + m) ಆಗಿರುತ್ತದೆ.