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) 哈希表。