2661。第一个完全绘制的行或列
难度：中等
主题：数组、哈希表、矩阵
给你一个0索引整数数组arr，和一个m x n整数矩阵 mat。 arr 和 mat 都包含 all 范围 [1, m * n] 内的整数。
从索引 0 开始遍历 arr 中的每个索引 i，并在包含整数 arr[i] 的 mat 中绘制单元格。
返回行或列将在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 5
- 1 5
- 1
- arr 的所有整数唯一.
- mat 的所有整数唯一.
提示：
- 我们可以使用频率数组吗？
- 预处理矩阵中值的位置。
- 遍历数组并使用预处理的位置递增相应的行和列频率。
- 如果行频率等于列数，反之亦然，返回当前索引。
解决方案：
我们可以按照以下步骤操作：
方法
-
预处理元素的位置:
- 首先，我们需要存储矩阵中元素的位置。我们可以创建一个字典 (position_map)，将矩阵中的每个值映射到其 (row, col) 位置。
-
频率数组:
- 我们需要两个频率数组：一个用于行，一个用于列。
- 当我们遍历 arr 数组时，我们将增加每个元素各自行和列的频率。
-
检查完整的行或列:
- 每次增量后，检查是否有行或列被完全绘制（即其频率达到矩阵列或行的大小）。
- 如果是，则返回当前索引。
-
返回结果:
详细步骤
- 为mat中的每个值创建一个映射position_map到它的(row, col)位置。
- 创建数组 row_count 和 col_count 来跟踪每行和列中绘制的单元格的数量。
- 遍历arr，对于每个元素，更新各自的行数和列数。
- 如果在任何时候行或列被完全绘制，则返回该索引。
让我们用 PHP 实现这个解决方案：2661。第一个完全绘制的行或列
<?php /**
* @param Integer[] $arr
* @param Integer[][] $mat
* @return Integer
*/
function firstCompleteIndex($arr, $mat) {
...
...
...
/**
* go to ./solution.php
*/
}
// Example usage:
$arr = [1, 3, 4, 2];
$mat = [[1, 4], [2, 3]];
echo firstCompleteIndex($arr, $mat); // Output: 2
$arr = [2, 8, 7, 4, 1, 3, 5, 6, 9];
$mat = [[3, 2, 5], [1, 4, 6], [8, 7, 9]];
echo firstCompleteIndex($arr, $mat); // Output: 3
?>
登录后复制
解释：
-
预处理位置:
- 我们构建一个字典position_map，其中mat中的每个值都映射到其（行，列）位置。这有助于在遍历 arr 的过程中，在常数时间内直接访问任意值的位置。
-
频率计数:
- 我们用零初始化 row_count 和 col_count 数组。这些数组将跟踪特定行或列中的单元格被绘制的次数。
-
遍历数组:
- 对于arr中的每个值，我们在position_map中查找其位置，然后递增相应的行数和列数。
- 更新计数后，我们检查是否有任何行或列已达到其完整大小（即 row_count[$row] == n 或 col_count[$col] == m）。如果是，我们返回当前索引 i。
-
返回结果:
时间复杂度：
-
预处理：我们在 O(m * n) 中构建position_map。
-
遍历：我们处理arr的每个元素（长度为m * n），对于每个元素，我们执行常数时间操作来更新和检查行频率和列频率，这需要O( 1) 时间。
- 总体来说，时间复杂度为O(m * n)。
空间复杂度：
- 我们将所有元素的位置存储在position_map中，并且我们使用O(m n)空间作为频率数组。因此，空间复杂度为O(m * n)。
该解决方案应该在给定的限制内有效地处理问题。
联系链接
如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！
如果您想要更多类似的有用内容，请随时关注我：
以上是第一个完全绘制的行或列的详细内容。更多信息请关注PHP中文网其他相关文章！
