2661、找出叠涂元素——哈希表
超时方法
首先，通过使用unordered_map来构建矩阵mat中元素与其索引的映射关系。遍历矩阵中的每个元素，将元素作为键，将其索引{i, j, 0}作为值，存储在matrix中。这样做的目的是方便后续根据元素值查找对应的索引。
接下来，遍历数组arr中的每个数，依次进行以下操作：
- 将当前数在
matrix中对应索引的第三个元素置为1，表示该数已经在数组arr中出现过。 - 初始化一个标志变量
flag为1，用于标记当前数所在行或列的所有数是否都在数组arr中出现过。 - 获取当前数在
matrix中对应的索引的行号y_pos和列号x_pos。 - 遍历当前数所在行的所有数，如果有任何一个数在
matrix中对应索引的第三个元素不等于1（即未在数组arr中出现过），则将flag置为0，并跳出循环。 - 如果
flag仍然为1，说明当前数所在行的所有数都在数组arr中出现过，返回当前数的索引。 - 如果
flag为0，继续下一步操作。 - 将
flag重新置为1。 - 遍历当前数所在列的所有数，如果有任何一个数在
matrix中对应索引的第三个元素不等于1（即未在数组arr中出现过），则将flag置为0，并跳出循环。 - 如果
flag仍然为1，说明当前数所在列的所有数都在数组arr中出现过，返回当前数的索引。 - 如果
flag为0，继续下一次循环。
class Solution {
public:
int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
unordered_map<int, vector<int>> matrix;
for(int i=0;i<mat.size();i ){
for(int j=0;j<mat[0].size();j ){
matrix[mat[i][j]] = {i, j, 0};
}
}
for(int i=0;i<arr.size();i ){
matrix[arr[i]][2] = 1;
int flag = 1;
int y_pos = matrix[arr[i]][0];
int x_pos = matrix[arr[i]][1];
for(int x=0;x<mat[0].size();x ){
if(matrix[mat[y_pos][x]][2] == 0){
flag = 0;
break;
}
}
if(flag == 1){
return i;
}
flag = 1;
for(int y=0;y<mat.size();y ){
if(matrix[mat[y][x_pos]][2] == 0){
flag = 0;
break;
}
}
if(flag == 1){
return i;
}else{
continue;
}
}
return 0;
}
};优化
将刚刚遍历 arr[i] 的行和列改为用哈希表存储行和列的被涂色的元素个数，每次涂色更新并检查该元素的行列中被涂色的元素个数，如果满一行或者一列，则返回 arr 的当前下标。
class Solution
{
public:
int firstCompleteIndex(vector<int> &arr, vector<vector<int>> &mat)
{
int h = mat.size();
int w = mat[0].size();
unordered_map<int, pair<int, int>> matrix;
unordered_map<int, int> row;
unordered_map<int, int> col;
for (int i = 0; i < h; i )
{
row[i] = 0;
for (int j = 0; j < w; j )
{
col[j] = 0;
matrix[mat[i][j]] = {i, j};
}
}
for (int i = 0; i < h * w; i )
{
int x_pos = matrix[arr[i]].second;
col[x_pos] ;
if (col[x_pos] == h)
{
return i;
}
int y_pos = matrix[arr[i]].first;
row[y_pos] ;
if (row[y_pos] == w)
{
return i;
}
}
return 0;
}
};------本页内容已结束，喜欢请分享------
