Medium

题目描述

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

A 和 B 的 前缀公共数组 是一个长度为 n 的数组 C，其中 C[i] 等于在索引 i 或之前在 A 和 B 中都出现的不同数字的数量。

返回 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：只有 3 在 A 和 B 中都出现，所以 C[1] = 1。
在 i = 2：1、2 和 3 在 A 和 B 中都出现，所以 C[2] = 3。

提示：

  • 1 <= A.length == B.length == n <= 50
  • 1 <= A[i], B[i] <= n
  • 保证 A 和 B 都是 n 个整数的排列

提示：

  • 考虑保持一个频率数组，存储每个数字到索引 i 的出现次数。
  • 如果一个数字出现了两次，说明它在 A 和 B 中都出现了（因为它们都是排列），所以将答案加一。

解题思路

这道题可以用多种方法求解，核心思路是动态维护已访问过的元素集合。

方法一：频率数组统计（推荐）

  • 使用频率数组 count 记录每个数字的出现次数
  • 遍历数组，对于每个位置 i，将 A[i] 和 B[i] 的计数加1
  • 当某个数字的计数达到2时，说明它在两个数组中都出现了，公共数字数量加1
  • 这种方法利用了数组是排列的特性，每个数字最多出现2次

方法二：位运算优化

  • 由于数字范围是1到n，可以用位掩码来记录已访问的数字
  • 当某位被设置两次时，表示该数字在两个数组中都出现

方法三：双哈希集合

  • 分别维护A和B的已访问元素集合，通过求交集得到公共元素数量

频率数组方法实现简单，空间复杂度固定，是最优解法。

代码实现

class Solution {
public:
    vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
        int n = A.size();
        vector<int> result(n);
        vector<int> count(n + 1, 0);
        int common = 0;
        
        for (int i = 0; i < n; i++) {
            count[A[i]]++;
            if (count[A[i]] == 2) common++;
            
            count[B[i]]++;
            if (count[B[i]] == 2) common++;
            
            result[i] = common;
        }
        
        return result;
    }
};

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

public class Solution {
    public int[] FindThePrefixCommonArray(int[] A, int[] B) {
        int n = A.Length;
        int[] result = new int[n];
        int[] count = new int[n + 1];
        int common = 0;
        
        for (int i = 0; i < n; i++) {
            count[A[i]]++;
            if (count[A[i]] == 2) common++;
            
            count[B[i]]++;
            if (count[B[i]] == 2) common++;
            
            result[i] = common;
        }
        
        return result;
    }
}

var findThePrefixCommonArray = function(A, B) {
    const n = A.length;
    const result = [];
    const count = new Array(n + 1).fill(0);
    let common = 0;
    
    for (let i = 0; i < n; i++) {
        count[A[i]]++;
        if (count[A[i]]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)只需要遍历一次数组，每次操作都是常数时间
空间复杂度O(n)需要额外的频率数组存储计数信息