求教一道题目

Given an m*n matrix of 1s and 0s, the value in it is either 1 or 0. 1 means there is a person; 0 means there is no person; If there are 2 or more people on the same row or the same column, then they can see each other. Return the number of people who can see others.
Example:
Inputs:
[
[1, 0, 0, 0],
[0, 0, 1, 1],
[0, 1, 0, 0],
[0, 1, 0, 0]
]
outputs:
4

我只想到了brute force的方法，请教一下有没有好的方法，谢谢🙏

能不能往dp方向想？

1. def solve(mat):
   
2.     """
   
3.     mat: 2D array, where the element is either 0 or 1.
   
4. 
   
5.     """
   
6.     n_row = len(mat)
   
7.     n_col = len(mat)
   
8.     row_counter = [0 for i in range(n_row)]
   
9.     col_counter = [0 for i in range(n_col)]
   
10.     for r in range(n_row):
    
11.         for c in range(n_col):
    
12.             if mat[r][c] == 1:
    
13.                 row_counter[r] += 1
    
14.                 col_counter[c] += 1
    
15.     num = sum(i if i>1 else 0 for i in row_counter) + sum(k if k > 1 else 0 for k in col_counter)
    
16.     for r in range(n_row):
    
17.         for c in range(n_col):
    
18.             if mat[r][c] == 1 and row_counter[r] > 1 and col_counter[c] > 1:
    
19.                 num -= 1
    
20.     return num
    

复制代码

O(MN) 的

夏虫何以语冰X 发表于 2020-12-6 21:56
我能想到的两种方法
1. 遍历每一个点，if(grid[j]==1 && valid(grid, i, j)) count++ 其中valid的方法就是 ...

还有一种方法是用set， 只记是1的点的坐标
当时被问到这道题，说了这两种方法之后，要求是利用每行每列person的个数，两个for循环，还有考虑一个人能否看到别人是由什么决定的（抱歉有点语焉不详， 这是我能记起的三个关键词）再做进一步优化

一个办法是按每行每列处理，如果遇到一行或者列里面1的个数大于1的话，就说明他们都能看到其他的人。用一个boolean[][]来代表每个人会不会看到其他人，这样可以去除重复计算。时间复杂度应该是O(n*m)。不知道你的brute force是不是类似的想法。

我能想到的两种方法
1. 遍历每一个点，if(grid[i][j]==1 && valid(grid, i, j)) count++ 其中valid的方法就是查看同一行和同一列中有没有1出现。当一个点能看到另外一个点，把这些点可以都加入visited中，这样可以减少一些重复visit
2. 或者直接按row扫一遍，按col扫一遍，符合要求的点加入visited来保证不重复记数。

感觉可以用union find？

flyman3046 发表于 2020-12-6 21:53
一个办法是按每行每列处理，如果遇到一行或者列里面1的个数大于1的话，就说明他们都能看到其他的人。用一个 ...

我的两个brute force的方法和三楼的一样，第一个就是对每个点，去遍历这个点所在的行和列；第二个就是遍历每行每列，用visited来减少重复。

不visit每一个点不可能知道这个点是否有人，所以不可能快于O(mn)。


2 pass:
Pass 1 row major: set记录1的i，j。如果一个row过完set内容大大于1，数上，mark visited。最多一个row全是1，所以速度最低2n每行。所有下来速度是2mn最多

Pass 2 col major: 一样的方法一列大于一个人开始数，但是逐一check是不是visit过，只加没visit过的。同样最多2mn

总体最多4mn，即O(mn)。无需继续优化因为离最快可能只最多只能提高4倍。

easy难度的题吧，预处理一下, O(mn)

上面说的都是需要记录visited，这样extra space就超过O(1)了(当然你也可以in place记录..)。实际上不需要特别记录visited，也可以做到时间O(mn), extra space O(1)