第一个完全绘制的行或列

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 的所有整数唯一.

提示：

1. 我们可以使用频率数组吗？
2. 预处理矩阵中值的位置。
3. 遍历数组并使用预处理的位置递增相应的行和列频率。
4. 如果行频率等于列数，反之亦然，返回当前索引。

解决方案：

我们可以按照以下步骤操作：

方法

1. 预处理元素的位置:

   • 首先，我们需要存储矩阵中元素的位置。我们可以创建一个字典 (position_map)，将矩阵中的每个值映射到其 (row, col) 位置。

2. 频率数组:

   • 我们需要两个频率数组：一个用于行，一个用于列。
   • 当我们遍历 arr 数组时，我们将增加每个元素各自行和列的频率。

3. 检查完整的行或列:

   • 每次增量后，检查是否有行或列被完全绘制（即其频率达到矩阵列或行的大小）。
   • 如果是，则返回当前索引。

4. 返回结果:

   • 行或列被完全绘制的索引就是我们的答案。

详细步骤

1. 为mat中的每个值创建一个映射position_map到它的(row, col)位置。
2. 创建数组 row_count 和 col_count 来跟踪每行和列中绘制的单元格的数量。
3. 遍历arr，对于每个元素，更新各自的行数和列数。
4. 如果在任何时候行或列被完全绘制，则返回该索引。

让我们用 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
?>

解释：

1. 预处理位置:

   • 我们构建一个字典position_map，其中mat中的每个值都映射到其（行，列）位置。这有助于在遍历 arr 的过程中，在常数时间内直接访问任意值的位置。

2. 频率计数:

   • 我们用零初始化 row_count 和 col_count 数组。这些数组将跟踪特定行或列中的单元格被绘制的次数。

3. 遍历数组:

   • 对于arr中的每个值，我们在position_map中查找其位置，然后递增相应的行数和列数。
   • 更新计数后，我们检查是否有任何行或列已达到其完整大小（即 row_count[$row] == n 或 col_count[$col] == m）。如果是，我们返回当前索引 i。

4. 返回结果:

   • 返回行或列完全绘制的第一个索引。

时间复杂度：

• 预处理：我们在 O(m * n) 中构建position_map。
• 遍历：我们处理arr的每个元素（长度为m * n），对于每个元素，我们执行常数时间操作来更新和检查行频率和列频率，这需要O( 1) 时间。
• 总体来说，时间复杂度为O(m * n)。

空间复杂度：

• 我们将所有元素的位置存储在position_map中，并且我们使用O(m n)空间作为频率数组。因此，空间复杂度为O(m * n)。

该解决方案应该在给定的限制内有效地处理问题。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是第一个完全绘制的行或列的详细内容。更多信息请关注PHP中文网其他相关文章！