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

implementation, https://leetcode.cn/problems/find-the-prefix-common-array-of-two-arrays/

给你两个下标从 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 个元素的排列。

这个问题可以通过多种方法解决。由于数组长度 $n$ 的范围较小（最大为 50），最直观的方法是使用计数数组或哈希表来记录每个数字出现的次数。

解题思路

由于 $A$ 和 $B$ 都是 $1$ 到 $n$ 的排列，这意味着在两个数组合并后的前缀中，如果某个数字出现了 2 次，则说明该数字在 $A$ 的前缀和 $B$ 的前缀中都出现过，即它是一个“公共元素”。

我们可以维护一个频率数组 freq 和一个计数器 common_count：

1. 遍历数组，下标为 i。
2. 将 $A[i]$ 出现的次数加 1。如果加完后次数变为 2，说明找到了一个公共元素，common_count 加 1。
3. 将 $B[i]$ 出现的次数加 1。如果加完后次数变为 2，说明找到了一个公共元素，common_count 加 1。
4. 将当前的 common_count 存入结果数组 C[i]。

Python 代码实现

from typing import List

class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
        n = len(A)
        res = [0] * n
        # freq 数组记录 1 到 n 每个数字出现的次数
        freq = [0] * (n + 1)
        common_count = 0
        
        for i in range(n):
            # 处理 A[i]
            freq[A[i]] += 1
            if freq[A[i]] == 2:
                common_count += 1
            
            # 处理 B[i]
            freq[B[i]] += 1
            if freq[B[i]] == 2:
                common_count += 1
            
            # 记录当前索引的前缀公共元素数量
            res[i] = common_count
            
        return res

复杂度分析

• 时间复杂度：$O(n)$。我们只需要遍历一次数组，每次循环内的操作（自增和判断）都是 $O(1)$ 的。
• 空间复杂度：$O(n)$。我们需要一个长度为 $n+1$ 的频率数组来记录数字出现的次数，以及一个长度为 $n$ 的结果数组。