题目

2657. 找到两个数组的前缀公共数组 - 力扣（LeetCode）

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

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

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

如果一个长度为 n 的数组包含 1 到 n 的元素恰好一次，我们称这个数组是一个长度为 n 的 排列 。

示例 1：

1
2
3
4
5
6
输入：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：

1
2
3
4
5
输入：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 个元素的排列。

解题

首先我们观察到，两个数组都分别是整数1到n的排列（数组中各元素互不相同）。

解题思路：

设所求数组为ans

从左到右遍历数组A和B，在每轮循环中：

  • 将A[i]和B[i]分别放入集合A以及集合B
  • 接着计算两个集合中相同元素的个数，将这个值赋给ans[i]

最后返回ans即可。

这里由于数组A和B的长度都不超过50，因此我们可以用位运算来优化操作。

用mask二进制位上的1和0来表示元素是否存在集合中，用 & 运算求出集合的交集，最后按照二进制位中1的个数来表示交集元素的数目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] findThePrefixCommonArray(int[] A, int[] B) {
        int len = A.length;
        long maska = 0;
        long maskb = 0;
        int[] ans = new int[len];
        for(int i = 0; i<len; i++) {
            // 将元素所在的位置加入集合mask中
            maska |= (1L << A[i]);	
            maskb |= (1L << B[i]);
			// 求出两个集合的交集，并且数出1的数量
            ans[i] = Long.bitCount(maska & maskb);
        }
        return ans;
    }
}