查找两个数组的前缀公共数组

2657。查找两个数组的前缀公共数组

难度：中等

主题：数组、哈希表、位操作

给你两个0索引长度为n的整数排列A和B。

A 和 B 的 A 前缀公共数组 是一个数组 C，使得 C[i] 等于 A 和 B 中索引 i 处或之前出现的数字的计数。

返回A和B的前缀公共数组。

如果 n 个整数的序列包含从 1 到 n 的所有整数恰好一次，则该序列称为

排列。

示例1：

• 输入： A = [1,3,2,4], B = [3,1,2,4]
• 输出： [0,2,3,4]
• 解释： 当 i = 0 时：没有公共数，因此 C[0] = 0。
  当 i = 1 时：1 和 3 在 A 和 B 中很常见，因此 C[1] = 2。
  当 i = 2 时：1、2 和 3 在 A 和 B 中很常见，因此 C[2] = 3。
  当 i = 3 时：1、2、3 和 4 在 A 和 B 中很常见，因此 C[3] = 4。

示例2：

• 输入： A = [2,3,1], B = [3,1,2]
• 输出： [0,1,3]
• 解释： 当 i = 0 时：没有公共数，因此 C[0] = 0。
  当 i = 1 时：A 和 B 中只有 3 是常见的，因此 C[1] = 1。
  当 i = 2 时：1、2 和 3 在 A 和 B 中很常见，因此 C[2] = 3。

约束：

1 1 保证A和B都是n个整数的排列。

提示：

考虑保留一个频率数组来存储每个数字出现的次数，直到索引 i。
如果一个数字出现了两次，则意味着它同时出现在 A 和 B 中，因为它们都是排列，所以在答案中加 1。

解决方案：

我们可以迭代两个数组 A 和 B，同时跟踪两个数组中当前索引处或之前出现的数字。由于两个数组都是同一组数字的排列，因此我们可以利用两个哈希集（或数组）来存储哪些数字出现在两个数组中的当前索引处或之前。对于每个索引，我们可以计算到目前为止两个数组中出现的公共数字。

解决办法：

1. 使用两个数组来跟踪 A 和 B 中直到索引 i 的数字的出现情况。
2. 对于每个索引 i，检查 A[i] 和 B[i] 之前是否已经见过。如果是这样，请增加公共计数。
3. 使用频率数组来跟踪两个数组中从 1 到 n 的数字的存在情况。

让我们用 PHP 实现这个解决方案：2657。查找两个数组的前缀公共数组

<?php /**
 * @param Integer[] $A
 * @param Integer[] $B
 * @return Integer[]
 */
function findThePrefixCommonArray($A, $B) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$A = [1, 3, 2, 4];
$B = [3, 1, 2, 4];
print_r(findThePrefixCommonArray($A, $B)); // Output: [0, 2, 3, 4]

$A = [2, 3, 1];
$B = [3, 1, 2];
print_r(findThePrefixCommonArray($A, $B)); // Output: [0, 1, 3]
?>

解释：

1. 频率数组：我们维护两个频率数组，freqA 和 freqB，其中每个索引代表排列中的一个数字。
   • 当我们在 A[i] 或 B[i] 中遇到数字时，我们会增加频率数组中对应的值。
2. 常见计数：更新 A[i] 和 B[i] 的频率数组后，我们检查每个数字是否出现在两个数组中直至索引 i。如果是这样，我们增加 commonCount。
3. 结果：公共计数存储在每个索引的结果数组中。

演练示例：

输入：

$A = [1, 3, 2, 4];
$B = [3, 1, 2, 4];

• 当 i = 0 时：还没有公共数 → C[0] = 0
• 当 i = 1 时：数字 1 和 3 是公共的 → C[1] = 2
• 当 i = 2 时：数字 1、2 和 3 是常见的 → C[2] = 3
• 在 i = 3 时：数字 1、2、3 和 4 是常见的 → C[3] = 4

输出：[0,2,3,4]

时间复杂度：

• O(n²⁾：对于每个索引 i，我们检查从 1 到 n 的每个元素以查看它是否常见，从而使该解决方案的时间复杂度呈二次方。考虑到约束 n ≤ 50.
，这是可以接受的

这应该在给定的约束下有效地工作。

联系链接

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

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

• 领英
• GitHub

以上是查找两个数组的前缀公共数组的详细内容。更多信息请关注PHP中文网其他相关文章！