이진 행렬 Leetcode 솔루션의 특수 위치

난이도 쉽게
자주 묻는 질문 구글
알고리즘 배열 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 매트릭스조회수 23

문제 정책

바이너리의 특수 위치 매트릭스 문제는 크기가 n * m 인 행렬이 주어 졌는데 여기에는 값 1과 0의 두 가지 유형 만 있습니다. 해당 셀의 값이 1이고 해당 특정 행과 열에있는 모든 셀의 값이 0이면 셀 위치를 special이라고합니다. 행렬에 몇 개의 특수 위치가 있는지 반환해야합니다.

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)에 대해 row (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인지 확인한 다음이 행과이 열의 개수가 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

자바 프로그램

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)입니다.

코멘트를 남겨

Translate »