题目描述
给你两个下标从 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 <= 501 <= A[i], B[i] <= n- 题目保证
A 和 B 两个数组都是 n 个元素的排列。
解法
方法一：计数
思考
两个排列的前缀公共元素个数。每次重建集合求交，\(n \le 50\) 可行，但前缀只增长一个元素。
分别计数 \(A\)、\(B\) 的出现，对值域 \([1,n]\) 取 \(\min\) 再求和，即当前公共个数。
我们可以使用两个数组 \(cnt1\) 和 \(cnt2\) 分别记录数组 \(A\) 和 \(B\) 中每个元素出现的次数，用数组 \(ans\) 记录答案。
遍历数组 \(A\) 和 \(B\)，将 \(A[i]\) 在 \(cnt1\) 中出现次数加一，将 \(B[i]\) 在 \(cnt2\) 中出现次数加一。然后枚举 \(j \in [1,n]\)，计算 \(cnt1\) 和 \(cnt2\) 中每个元素 \(j\) 出现次数的最小值，累加到 \(ans[i]\) 中。
遍历结束后，返回答案数组 \(ans\) 即可。
时间复杂度 \(O(n^2)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是数组 \(A\) 和 \(B\) 的长度。
| class Solution:
def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
ans = []
cnt1 = Counter()
cnt2 = Counter()
for a, b in zip(A, B):
cnt1[a] += 1
cnt2[b] += 1
t = sum(min(v, cnt2[x]) for x, v in cnt1.items())
ans.append(t)
return ans
|
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 n = A.length;
int[] ans = new int[n];
int[] cnt1 = new int[n + 1];
int[] cnt2 = new int[n + 1];
for (int i = 0; i < n; ++i) {
++cnt1[A[i]];
++cnt2[B[i]];
for (int j = 1; j <= n; ++j) {
ans[i] += Math.min(cnt1[j], cnt2[j]);
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | class Solution {
public:
vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
int n = A.size();
vector<int> ans(n);
vector<int> cnt1(n + 1), cnt2(n + 1);
for (int i = 0; i < n; ++i) {
++cnt1[A[i]];
++cnt2[B[i]];
for (int j = 1; j <= n; ++j) {
ans[i] += min(cnt1[j], cnt2[j]);
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | func findThePrefixCommonArray(A []int, B []int) []int {
n := len(A)
cnt1 := make([]int, n+1)
cnt2 := make([]int, n+1)
ans := make([]int, n)
for i, a := range A {
b := B[i]
cnt1[a]++
cnt2[b]++
for j := 1; j <= n; j++ {
ans[i] += min(cnt1[j], cnt2[j])
}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | function findThePrefixCommonArray(A: number[], B: number[]): number[] {
const n = A.length;
const cnt1: number[] = Array(n + 1).fill(0);
const cnt2: number[] = Array(n + 1).fill(0);
const ans: number[] = Array(n).fill(0);
for (let i = 0; i < n; ++i) {
++cnt1[A[i]];
++cnt2[B[i]];
for (let j = 1; j <= n; ++j) {
ans[i] += Math.min(cnt1[j], cnt2[j]);
}
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | impl Solution {
pub fn find_the_prefix_common_array(a: Vec<i32>, b: Vec<i32>) -> Vec<i32> {
let n = a.len();
let mut ans = vec![0; n];
let mut cnt1 = vec![0; n + 1];
let mut cnt2 = vec![0; n + 1];
for i in 0..n {
cnt1[a[i] as usize] += 1;
cnt2[b[i] as usize] += 1;
for j in 1..=n {
ans[i] += std::cmp::min(cnt1[j], cnt2[j]);
}
}
ans
}
}
|
方法二：位运算（异或运算）
思考
方法一每步 \(O(n)\) 扫值域。排列中每个值恰出现两次（两个数组各一次），用 \(vis\) 异或翻转：第二次见到时公共数加一，从而 \(O(1)\) 更新。
我们可以使用一个长度为 \(n+1\) 的数组 \(vis\) 记录数组 \(A\) 和 \(B\) 中每个元素的出现情况，数组 \(vis\) 的初始值为 \(1\)。另外，我们用一个变量 \(s\) 记录当前公共元素的个数。
接下来，我们遍历数组 \(A\) 和 \(B\)，更新 \(vis[A[i]] = vis[A[i]] \oplus 1\)，并且更新 \(vis[B[i]] = vis[B[i]] \oplus 1\)，其中 \(\oplus\) 表示异或运算。
如果遍历到当前位置，元素 \(A[i]\) 出现过两次（即在数组 \(A\) 和 \(B\) 中都出现过），那么 \(vis[A[i]]\) 的值将为会 \(1\)，我们将 \(s\) 加一。同理，如果元素 \(B[i]\) 出现过两次，那么 \(vis[B[i]]\) 的值将为会 \(1\)，我们将 \(s\) 加一。然后将 \(s\) 的值加入到答案数组 \(ans\) 中。
遍历结束后，返回答案数组 \(ans\) 即可。
时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是数组 \(A\) 和 \(B\) 的长度。
1
2
3
4
5
6
7
8
9
10
11
12 | class Solution:
def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
ans = []
vis = [1] * (len(A) + 1)
s = 0
for a, b in zip(A, B):
vis[a] ^= 1
s += vis[a]
vis[b] ^= 1
s += vis[b]
ans.append(s)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | class Solution {
public int[] findThePrefixCommonArray(int[] A, int[] B) {
int n = A.length;
int[] ans = new int[n];
int[] vis = new int[n + 1];
Arrays.fill(vis, 1);
int s = 0;
for (int i = 0; i < n; ++i) {
vis[A[i]] ^= 1;
s += vis[A[i]];
vis[B[i]] ^= 1;
s += vis[B[i]];
ans[i] = s;
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | class Solution {
public:
vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
int n = A.size();
vector<int> ans;
vector<int> vis(n + 1, 1);
int s = 0;
for (int i = 0; i < n; ++i) {
vis[A[i]] ^= 1;
s += vis[A[i]];
vis[B[i]] ^= 1;
s += vis[B[i]];
ans.push_back(s);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | func findThePrefixCommonArray(A []int, B []int) (ans []int) {
vis := make([]int, len(A)+1)
for i := range vis {
vis[i] = 1
}
s := 0
for i, a := range A {
b := B[i]
vis[a] ^= 1
s += vis[a]
vis[b] ^= 1
s += vis[b]
ans = append(ans, s)
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | function findThePrefixCommonArray(A: number[], B: number[]): number[] {
const n = A.length;
const vis: number[] = Array(n + 1).fill(1);
const ans: number[] = [];
let s = 0;
for (let i = 0; i < n; ++i) {
const [a, b] = [A[i], B[i]];
vis[a] ^= 1;
s += vis[a];
vis[b] ^= 1;
s += vis[b];
ans.push(s);
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | impl Solution {
pub fn find_the_prefix_common_array(a: Vec<i32>, b: Vec<i32>) -> Vec<i32> {
let n = a.len();
let mut ans = vec![0; n];
let mut vis = vec![1; n + 1];
let mut s = 0;
for i in 0..n {
vis[a[i] as usize] ^= 1;
s += vis[a[i] as usize];
vis[b[i] as usize] ^= 1;
s += vis[b[i] as usize];
ans[i] = s;
}
ans
}
}
|
方法三：位运算（空间优化）
思考
方法二仍用 \(O(n)\) 数组。\(n \le 50\)，可用两个整数作位集，前缀或运算后 bit_count(x & y) 即公共个数，额外空间降为常数。
由于题目中给定的数组 \(A\) 和 \(B\) 的元素范围是 \([1,n]\)，且不超过 \(50\)，我们可以使用一个整数 \(x\) 和一个整数 \(y\) 来分别表示数组 \(A\) 和 \(B\) 中每个元素的出现情况。具体地，我们用整数 \(x\) 的第 \(i\) 位表示元素 \(i\) 是否在数组 \(A\) 中出现过，用整数 \(y\) 的第 \(i\) 位表示元素 \(i\) 是否在数组 \(B\) 中出现过。
时间复杂度 \(O(n)\)，其中 \(n\) 是数组 \(A\) 和 \(B\) 的长度。空间复杂度 \(O(1)\)。
| class Solution:
def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
ans = []
x = y = 0
for a, b in zip(A, B):
x |= 1 << a
y |= 1 << b
ans.append((x & y).bit_count())
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13 | class Solution {
public int[] findThePrefixCommonArray(int[] A, int[] B) {
int n = A.length;
int[] ans = new int[n];
long x = 0, y = 0;
for (int i = 0; i < n; i++) {
x |= 1L << A[i];
y |= 1L << B[i];
ans[i] = Long.bitCount(x & y);
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | class Solution {
public:
vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
int n = A.size();
vector<int> ans(n);
long long x = 0, y = 0;
for (int i = 0; i < n; ++i) {
x |= (1LL << A[i]);
y |= (1LL << B[i]);
ans[i] = __builtin_popcountll(x & y);
}
return ans;
}
};
|
| func findThePrefixCommonArray(A []int, B []int) []int {
n := len(A)
ans := make([]int, n)
var x, y int
for i := 0; i < n; i++ {
x |= 1 << A[i]
y |= 1 << B[i]
ans[i] = bits.OnesCount(uint(x & y))
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | function findThePrefixCommonArray(A: number[], B: number[]): number[] {
const n = A.length;
const ans: number[] = [];
let [x, y] = [0n, 0n];
for (let i = 0; i < n; i++) {
x |= 1n << BigInt(A[i]);
y |= 1n << BigInt(B[i]);
ans.push(bitCount64(x & y));
}
return ans;
}
function bitCount64(i: bigint): number {
i = i - ((i >> 1n) & 0x5555555555555555n);
i = (i & 0x3333333333333333n) + ((i >> 2n) & 0x3333333333333333n);
i = (i + (i >> 4n)) & 0x0f0f0f0f0f0f0f0fn;
i = i + (i >> 8n);
i = i + (i >> 16n);
i = i + (i >> 32n);
return Number(i & 0x7fn);
}
|
1
2
3
4
5
6
7
8
9
10
11
12 | impl Solution {
pub fn find_the_prefix_common_array(a: Vec<i32>, b: Vec<i32>) -> Vec<i32> {
let mut ans = Vec::with_capacity(a.len());
let (mut x, mut y): (u64, u64) = (0, 0);
for (&a_val, &b_val) in a.iter().zip(b.iter()) {
x |= 1 << a_val;
y |= 1 << b_val;
ans.push((x & y).count_ones() as i32);
}
ans
}
}
|