本文介绍: 使用两个数组记录每个行或列被涂的次数,因为所有数字不相等,所以不会重复涂。遍历arr判断arr[i]所在行或所在列被涂满,就返回i使用哈希保存arr[i]的行和列以便遍历时可用快速取出;的某一行或某一列上都被涂色且下标最小元素,并返回下标

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;
    }
};

原文地址:https://blog.csdn.net/m0_52043808/article/details/134731956

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_27646.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注