二进制矩阵Leetcode解决方案中的特殊位置


难度级别 易得奖学金
经常问 谷歌
排列 矩阵

问题陈述

在二进制中的特殊位置 矩阵 问题给出了大小为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),我们将完全遍历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

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

二进制矩阵Leetcode解决方案中特殊位置的复杂性分析

时间复杂度

O(n * m *(n + m)): 在最坏的情况下,我们遍历矩阵中的每个单元格的行和列,即O(n + m)。 因此,时间复杂度将为O(n * m *(n + m))。

空间复杂度 

O(1): 我们在这里不使用任何额外的内存。

优化方法

我们可以通过执行一些预处理将每个单元的线性工作减少到恒定时间来优化上述方法。
我们可以做的是,起初我们可以将每个行和每一列的1计数存储在两个线性数组中。 然后,我们遍历每个单元格并检查其值是否为1,然后检查此行和此列中的1s计数是否等于4,或者不使用count数组。 通过检查特定的行和列,我们现在可以在恒定时间内执行此操作。 那是使用一些额外的内存的好处,它可以减少时间复杂度。 下图显示了一个4 * XNUMX矩阵的示例:

二进制矩阵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

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

二进制矩阵Leetcode解决方案中特殊位置的复杂性分析

时间复杂度

O(n * m): 在这里,我们运行两个嵌套循环以查找1的数量。 即O(2 * n * m)。 然后我们遍历矩阵的每个单元,取O(n * m)。 因此,总体时间复杂度将为O(n * m)。

空间复杂度 

O(n + m): 我们使用了大小为n和m的两个线性数组。 因此,空间复杂度将为O(n + m)。