2023-12-01每日一题

一、题目编号

2661. 找出叠涂元素

二、题目链接

点击跳转到题目位置

三、题目描述

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

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

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

示例 1：

示例 2：

提示：

• m == mat.length
• n = mat[i].length
• arr.length == m * n
• 1 <= m, n <= 10⁵
• 1 <= m * n <= 10⁵
• 1 <= arr[i], mat[r][c] <= m * n
• arr 中的所有整数 互不相同
• mat 中的所有整数 互不相同

四、解题代码

class Solution {
    unordered_map<int, int> line;
    unordered_map<int, int> row;
    unordered_map<int, int> row1;
    unordered_map<int, int> line1;
public:
    int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();
        int len = arr.size();
        int judge_row = n;
        int judge_line = m;
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                row1[mat[i][j]] = i;
                line1[mat[i][j]] = j;
            }
        }
        for(int i = 0; i < len; ++i){
            int x = row1[arr[i]];
            int y = line1[arr[i]];
            row[x]++;
            line[y]++;
            if(row[x] == judge_row || line[y] == judge_line){
                return i;
            }
        }
    return 0;
    }
};

五、解题思路

(1) 哈希表。