哈希表 LeetCode 2661. 找出叠涂元素

2661. 找出叠涂元素

给你一个下标从 0 开始的整数数组 arr 和一个 m x n 的整数 矩阵 mat 。arr 和 mat 都包含范围 [1，m * n] 内的 所有 整数。

从下标 0 开始遍历 arr 中的每个下标 i ，并将包含整数 arr[i] 的 mat 单元格涂色。

请你找出 arr 中在 mat 的某一行或某一列上都被涂色且下标最小的元素，并返回其下标 i 。

 遍历arr，判断arr[i]所在行或所在列被涂满，就返回i。

使用哈希表保存arr[i]的行和列，以便在遍历时可用快速取出；

使用两个数组来记录每个行或列被涂的次数，因为所有数字不相等，所以不会重复涂。

class Solution {
public:
    int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();
        unordered_map<int,int>r;
        unordered_map<int,int>c;
        vector<int>cnt_r(m,0);
        vector<int>cnt_c(n,0);
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
              r[mat[i][j]]=i;
              c[mat[i][j]]=j;
            }
        }
        for(int i=0;i<arr.size();i++){
            int ri=r[arr[i]];
            int ci=c[arr[i]];
            cnt_r[ri]++;
            cnt_c[ci]++;
            if(cnt_r[ri]==n||cnt_c[ci]==m)return i;
        }
        return -1;
    }
};