Problem: 2661. 找出叠涂元素
思路:中途检查
解法
- 数据量不大,看着可以在每次涂色时候查询是否合法
- 但是每次都查询显然会超时,我们选择一个更有效的优化
- 已经说明各个数各不相同,不会出现一个格子被涂两遍的情况
- 我们用数组来记录每一行和每一列已经被涂的格子数量,就能知道这一行列是否被全涂满
时间复杂度: $O(m*n)$
空间复杂度: $O(m*n)$
Code
class Solution:
def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
matMap={}
m=len(mat)
n=len(mat[0])
row=[0]*m
col=[0]*n
for i in range(m):
for j in range(n):
matMap[mat[i][j]]=(i,j)
for index in range(len(arr)):
num=arr[index]
x,y=matMap[num]
row[x]+=1
col[y]+=1
if row[x]==n or col[y]==m:
return index
return -1
思路:最后查询
解法
- 我们注意到当我们知道某一行的所有元素的时候,变相知道了这一行会被什么时候涂满,既这一行存在arr中最靠后的那个索引
- 所以我们的任务变成了寻找最先被涂满的行或者列
- 对arr进行hash,记录每个元素的具体位置,再遍历行列,在遍历过程中
- 行列取最大值表示让这一行填满最少需要的步数
- res取上述的数的最小值 时间复杂度: $O(mn)$ 空间复杂度: $O(mn)$
Code
class Solution {
public:
int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
int res=arr.size();
unordered_map<int,int>hash;
for (int i=0;i<arr.size();i++){
hash[arr[i]]=i;
}
for (int i=0;i<mat.size();i++){
int tmp=0;
for (int j=0;j<mat[0].size();j++){
tmp=max(tmp,hash[mat[i][j]]);
}
res=min(res,tmp);
}
for (int j=0;j<mat[0].size();j++){
int tmp=0;
for (int i=0;i<mat.size();i++){
tmp=max(tmp,hash[mat[i][j]]);
}
res=min(res,tmp);
}
return res;
}
};
class Solution:
def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
res=len(arr)
m=len(mat)
n=len(mat[0])
arrLocation={}
for i,a in enumerate(arr):
arrLocation[a]=i
for i in range(m):
nowColNeedSteps=0
for j in range(n):
nowColNeedSteps=max(nowColNeedSteps,arrLocation[mat[i][j]])
res=min(res,nowColNeedSteps)
for j in range(n):
nowRowNeedSteps=0
for i in range(m):
nowRowNeedSteps=max(nowRowNeedSteps,arrLocation[mat[i][j]])
res=min(res,nowRowNeedSteps)
return res