题解-找出叠涂元素-哈希表,两种思路,在途中检查和在最后检查
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