题解-找出叠涂元素-哈希表,两种思路,在途中检查和在最后检查

Problem: 2661. 找出叠涂元素

• 思路:中途检查
  • 解法
  • Code
• 思路:最后查询
  • 解法
  • Code

思路:中途检查

解法

• 数据量不大,看着可以在每次涂色时候查询是否合法
• 但是每次都查询显然会超时,我们选择一个更有效的优化
• 已经说明各个数各不相同,不会出现一个格子被涂两遍的情况
• 我们用数组来记录每一行和每一列已经被涂的格子数量,就能知道这一行列是否被全涂满

时间复杂度:

空间复杂度:
## 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取上述的数的最小值
时间复杂度:
空间复杂度:
## 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