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

难度: Medium

给你两个下标从 0 开始长度为 n 的整数排列 A 和 B 。

A 和 B 的 前缀公共数组 定义为数组 C ，其中 C[i] 是数组 A 和 B 到下标为 i 之前公共元素的数目。

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

如果一个长度为 n 的数组包含 1 到 n 的元素恰好一次，我们称这个数组是一个长度为 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 是两个数组的前缀公共元素，所以 C[1] = 2 。
i = 2：1，2 和 3 是两个数组的前缀公共元素，所以 C[2] = 3 。
i = 3：1，2，3 和 4 是两个数组的前缀公共元素，所以 C[3] = 4 。

示例 2：

输入：A = [2,3,1], B = [3,1,2]
输出：[0,1,3]
解释：i = 0：没有公共元素，所以 C[0] = 0 。
i = 1：只有 3 是公共元素，所以 C[1] = 1 。
i = 2：1，2 和 3 是两个数组的前缀公共元素，所以 C[2] = 3 。

提示：

1 <= A.length == B.length == n <= 50
1 <= A[i], B[i] <= n
题目保证 A 和 B 两个数组都是 n 个元素的排列。

Submission

运行时间: 33 ms

内存: 16.0 MB

from typing import List

class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
        n = len(A)
        prefix_common = [0] * n
        count = 0
        seen = set()
        
        for i in range(n):
            if A[i] in seen:
                count += 1
            seen.add(A[i])
            
            if B[i] in seen:
                count += 1
            seen.add(B[i])
            
            prefix_common[i] = count
        
        return prefix_common

from typing import List

class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
        n = len(A)
        prefix_common = [0] * n
        count_A = 0
        count_B = 0
        seen_A = set()
        seen_B = set()
        
        for i in range(n):
            if A[i] in seen_B:
                count_A += 1
            seen_A.add(A[i])
            
            if B[i] in seen_A:
                count_B += 1
            seen_B.add(B[i])
            
            prefix_common[i] = count_A + count_B
        
        return prefix_common

Explain

题解的核心思路在于利用两个集合来跟踪数组A和B中已经见过的元素。对于每个索引i，我们检查数组A和B的当前元素是否已经在对方的集合中出现过。如果是，相应的计数器（count_A或count_B）增加。这两个计数器分别跟踪A的元素在B的前缀中出现的次数和B的元素在A的前缀中出现的次数。最后，将这两个计数器的和存储在结果数组的相应位置。这种方法确保了即便元素以不同的顺序出现，也能正确计算出前缀中共有元素的数量。

时间复杂度: O(n)

空间复杂度: O(n)

from typing import List

class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
        n = len(A)
        prefix_common = [0] * n  # 结果数组，记录每个位置的前缀公共元素数量
        count_A = 0  # 记录A的元素在B的前缀中出现的次数
        count_B = 0  # 记录B的元素在A的前缀中出现的次数
        seen_A = set()  # 记录A中已经出现的元素
        seen_B = set()  # 记录B中已经出现的元素
        
        for i in range(n):
            if A[i] in seen_B:  # 如果A中当前元素已在B的前缀中出现
                count_A += 1
            seen_A.add(A[i])  # 添加当前元素到A的已见集
            
            if B[i] in seen_A:  # 如果B中当前元素已在A的前缀中出现
                count_B += 1
            seen_B.add(B[i])  # 添加当前元素到B的已见集
            
            prefix_common[i] = count_A + count_B  # 计算当前的前缀公共元素数量
        
        return prefix_common

Explore

在这个算法中，使用两个计数器count_A和count_B是为了独立跟踪数组A中的元素在数组B的前缀中出现的次数，以及数组B中的元素在数组A的前缀中出现的次数。这样做可以确保每个数组的元素在对方数组中的每一次出现都被正确计数，尤其是在处理前缀时，这一点尤为重要。使用单一计数器可能导致某些情况下的错误统计，例如一方的元素在另一方前缀中多次出现可能会被重复计数或遗漏。

如果数组A和B的长度不同，当前算法将无法直接适用，因为它假设两个数组具有相同的长度n，并在同一循环中同时遍历这两个数组。此外，如果数组包含重复元素或不是从1到n的整数集，算法仍可以正确地计算交叉出现的次数，因为它是基于集合成员资格来判断元素是否已在另一数组的前缀中出现过。不过，对于不同长度的数组，需要调整算法以处理长度不一的情况，可能通过填充较短数组或修改循环逻辑来实现。

算法对于元素的出现顺序是敏感的。因为算法是依赖于元素在数组中的位置来决定其是否已在对方数组的前缀中出现过。如果两个数组的元素相同但顺序完全相反，计数器的增加将在不同的时间点发生，因此输出的前缀公共数组将会不同。例如，如果一个数组是另一个数组的逆序，那么每次比较时，前缀交叉出现的情况将会更少，直到最后一个元素才可能出现最多的交叉点。

在题解中使用的集合seen_A和seen_B是为了跟踪已经在各自数组中出现过的元素，使用集合是因为集合自动处理重复元素的问题，即集合会忽略重复添加的元素。因此，当元素被添加到集合中时，不需要显式检查该元素是否已存在于集合中，因为如果元素已存在，集合不会再次添加它。这样可以保持代码的简洁性和效率。