【每日一题】找出叠涂元素

Tag

【哈希表】【数组】【2023-12-01】

题目来源

2661. 找出叠涂元素

题目解读

从左往右遍历 arr 给矩阵 mat 上色，在上色的过程中矩阵的某一行或者某一列的全部被上色了，返回此时的 i。

解题思路

本题难度不大，就是题目意思有点不容易理解，相信大家在理解了我的题目解读之后，就会明白题目的含义。

方法一：哈希表

为方便表述，记 n 为矩阵 mat 的行数，m 为矩阵的列数。

整体思路

我们需要判断某一行或者某一列是否被全部涂色，如是则返回让这一行或者这一列被全部涂色的最后一个整数在数组 arr 中对应的下标。

于是，我们需要遍历数组 arr，看看是哪一个下标对应的整数，将矩阵 mat 的某一行或某一列涂满色。

首先需要使用哈希表或者数组来统计mat中每一个整数对应的行和列，下方代码中使用的是数组 num2Idx 来统计：数组的下标表示mat中的整数，值对应 i * m + j，i 表示整数在 mat 中的行索引，j 表示列索引。还要维护两个数组 rowCnt 和 colCnt，rowCnt[i] 表示矩阵第 i 行被涂色的格子数，colCnt 表示矩阵第 j 行被涂色的格子数。

接着从左往右遍历数组 arr 中的整数 num，根据 num2Idx[num] 更新数组 rowCnt 和 colCnt，如果某一行或者某一列被涂满色，则返回 num 在 arr 中的索引。

实现代码

class Solution {
public:
    int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size();
        vector<int> num2Idx(n * m + 1);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                num2Idx[mat[i][j]] = i * m + j;
            }
        }

        vector<int> rowCnt(n, 0), colCnt(m, 0);
        for (int i = 0; i < arr.size(); ++i) {
            int num = arr[i];
            int row = num2Idx[num] / m, col = num2Idx[num] % m;
            if (++rowCnt[row] == m) {
                return i;
            }
            if (++colCnt[col] == n) {
                return i;
            }
        }
        return -1;
    }
};

复杂度分析

时间复杂度：$O(n\times m)$，$n$ 是矩阵 mat 的宽度，$m$ 是矩阵的高度。

空间复杂度：$O(n\times m)$。

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。

最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。