题目描述
给你一个下标从 0 开始的整数数组 arr 和一个 m x n 的整数 矩阵 mat 。arr 和 mat 都包含范围 [1,m * n] 内的 所有 整数。
从下标 0 开始遍历 arr 中的每个下标 i ,并将包含整数 arr[i] 的 mat 单元格涂色。
请你找出 arr 中在 mat 的某一行或某一列上都被涂色且下标最小的元素,并返回其下标 i 。
思路
开两个数组,长度分别为m和n,记录每一行的已经涂过的元素的数量和每一列的已经涂过的元素的数量
再开一个长度为(m * n + 1)数组记录mat的每个元素的行,列下标
遍历mat记录每个下标
遍历arr,并将对应的行,列数组 ++
当某一行/一列的数量等于列元素数量/行元素数量时跳出循环
C++ 代码
class Solution {
public:
int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
vector<int> row(m, 0);
vector<int> list(n, 0);
vector<pair<int, int>> sub(n * m + 1);
for (int i = 0; i < m; i ++)
for (int j = 0; j < n; j ++)
sub[mat[i][j]] = {i, j};
int idx;
for (idx = 0; idx < m * n; idx ++)
{
auto x = sub[arr[idx]].first, y = sub[arr[idx]].second;
row[x] ++, list[y] ++;
if (row[x] == n || list[y] == m) break;
}
return idx;
}
};