2661. 找出叠涂元素

🟠   🔖  数组 哈希表 矩阵  🔗 力扣 LeetCode

题目

You are given a 0-indexed integer array arr, and an m x n integer matrix mat. arr and mat both contain all the integers in the range [1, m * n].

Go through each index i in arr starting from index 0 and paint the cell in mat containing the integer arr[i].

Return the smallest index i at which either a row or a column will be completely painted in mat.

Example 1:


Input: arr = [1,3,4,2], mat = [[1,4],[2,3]]

Output: 2

Explanation: The moves are shown in order, and both the first row and second column of the matrix become fully painted at arr[2].

Example 2:

image explanation for example 2

Input: arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[8,7,9]]

Output: 3

Explanation: The second column becomes fully painted at arr[3].

Constraints:

• 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
• All the integers of arr are unique.
• All the integers of mat are unique.

题目大意

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

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

请你找出 arr 中第一个使得 mat 的某一行或某一列都被涂色的元素，并返回其下标 i 。

示例 1：

image explanation for example 1

输入： arr = [1,3,4,2], mat = [[1,4],[2,3]]

输出： 2

解释： 遍历如上图所示，arr[2] 在矩阵中的第一行或第二列上都被涂色。

示例 2：

image explanation for example 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 中的所有整数 互不相同

解题思路

1. 预处理：构建位置映射

   • 将矩阵的每个值的行、列索引记录到一个哈希表中，以便快速找到 arr[i] 在矩阵中的位置。

2. 初始化计数数组

   • 使用两个数组 rowCount 和 colCount 分别记录矩阵中每一行和每一列已涂色的单元格数。

3. 模拟涂色过程

   • 遍历 arr，对于每个值，根据映射找到其在矩阵中的行和列索引。
   • 更新对应的 rowCount 和 colCount。
   • 检查当前行或列是否完全涂满，如果是，直接返回当前的操作步骤。

复杂度分析

• 时间复杂度：O(m * n + k)
  • 预处理位置映射：O(m * n)，其中 m 和 n 分别是矩阵的行数和列数。
  • 模拟涂色过程：O(k)，k 是 arr 的长度。
  • 总复杂度为 O(m * n + k)。
• 空间复杂度：O(m + n + m*n)，使用了两个计数数组 rowCount 和 colCount，以及一个映射表。

代码

/**
 * @param {number[][]} grid
 * @param {number[]} arr
 * @return {number}
 */
var firstCompleteIndex = function (grid, arr) {
	const m = grid.length,
		n = grid[0].length;

	// 映射每个值到它在矩阵中的位置
	const valueToPosition = new Map();
	for (let i = 0; i < m; i++) {
		for (let j = 0; j < n; j++) {
			valueToPosition.set(grid[i][j], [i, j]);
		}
	}

	// 初始化行和列的计数器
	const rowCount = new Array(m).fill(0);
	const colCount = new Array(n).fill(0);

	// 遍历数组，模拟涂色
	for (let step = 0; step < arr.length; step++) {
		const value = arr[step];
		const [row, col] = valueToPosition.get(value);

		// 更新行和列的计数
		rowCount[row]++;
		colCount[col]++;

		// 检查是否有行或列被完全涂满
		if (rowCount[row] === n || colCount[col] === m) {
			return step; // 返回从 0 开始的索引
		}
	}
};

相关题目

题号	标题	题解	标签	难度	力扣
2133	检查是否每一行每一列都包含全部整数	[✓]	数组 哈希表 矩阵	🟢	🀄️ 🔗
2482	行和列中一和零的差值		数组 矩阵 模拟	🟠	🀄️ 🔗