『LeetCode』2661 找出叠涂元素

题目

2661. 找出叠涂元素

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

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

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

示例 1： >

输入：arr = [1,3,4,2], mat = [[1,4],[2,3]]
输出：2
解释：遍历如上图所示，arr[2] 在矩阵中的第一行或第二列上都被涂色。

示例 2： >

输入：arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[8,7,9]]
输出：3
解释：遍历如上图所示，arr[3] 在矩阵中的第二列上都被涂色。

提示：

\(m == mat.length\)
\(n = mat[i].length\)
\(arr.length == m * n\)
\(1 <= m, n <= 10^{5}\)
\(1 <= m * n <= 10^{5}\)
\(1 <= arr[i], mat[r][c] <= m * n\)
\(arr\) 中的所有整数 互不相同
\(mat\) 中的所有整数 互不相同

题解

【找出叠涂元素】简单哈希模拟

模拟

题目难点在于理解题意，逐个给矩阵上色，在给某个位置上色后如果满足该位置所在行或者该位置所在列全部都上色了，那么就返回该位置的下标。

剩余的工作就是模拟上色即可，为了快速知道上色位置是在哪，我们可以将矩阵的值与对应位置存到哈希表中，并用两个数组分布记录每行和每列上色的数量，即可确定某个位置上色后是否满足一行或一列全部上色的要求。

由于给定矩阵的取值范围不超过 \(n \times m\), 所以可以用个固定大小的数组作为哈希表，比用内置的哈希表要快些

# Code language: Python
class Solution:
    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
        n, m = len(mat), len(mat[0])
        st = {v: (i, j) for i, row in enumerate(mat) for j, v in enumerate(row)}
        cntRow, cntCol = [0] * n, [0] * m
        for idx, v in enumerate(arr):
            x, y = st[v]
            cntRow[x] += 1
            cntCol[y] += 1
            if cntRow[x] == m or cntCol[y] == n:
                return idx
        return -1

// Code language: Java
class Solution {
    public int firstCompleteIndex(int[] arr, int[][] mat) {
        int n = mat.length, m = mat[0].length;
        int[][] st = new int[n * m + 7][2];
        int[] cntRow = new int[n], cntCol = new int[m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                st[mat[i][j]][0] = i;
                st[mat[i][j]][1] = j;
            }
        }
        for (int i = 0; i < arr.length; i++) {
            int x = st[arr[i]][0], y = st[arr[i]][1];
            if (++cntRow[x] == m || ++cntCol[y] == n) {
                return i;
            }
        }
        return -1;
    }
}

// Code language: C++
class Solution {
public:
    int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size();
        vector<vector<int>> st(n * m + 7, vector(2, 0));
        vector<int> cntRow(n), cntCol(m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                st[mat[i][j]][0] = i;
                st[mat[i][j]][1] = j;
            }
        }
        for (int i = 0; i < arr.size(); i++) {
            int x = st[arr[i]][0], y = st[arr[i]][1];
            if (++cntRow[x] == m || ++cntCol[y] == n) {
                return i;
            }
        }
        return -1;
    }
};

// Code language: Go
func firstCompleteIndex(arr []int, mat [][]int) int {
    type pair struct {
        x, y int
    }
    var n, m = len(mat), len(mat[0])
    st := make([]pair, n * m + 1)
    cntRow := make([]int, n)
    cntCol := make([]int, m)
    for i, row := range mat {
        for j, v := range row {
            st[v] = pair{i, j}
        }
    }
    for idx, v := range arr {
        loc := st[v]
        if cntRow[loc.x]++; cntRow[loc.x] == m {
            return idx
        }
        if cntCol[loc.y]++; cntCol[loc.y] == n {
            return idx
        }
    }
    return -1
}

时间复杂度: \(O(n \times m + s)\), \(n, m\) 分别表示矩阵的长宽，\(s\) 表示 \(arr\) 数组的长度
空间复杂度: \(O(n \times m)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』2661 找出叠涂元素

题目

标签

题解

模拟