跳至主要內容

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

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

🟠   🔖  位运算 数组 哈希表  🔗 力扣open in new window LeetCodeopen in new window

题目

You are given two 0-indexed integer**** permutations A and B of length n.

A prefix common array of A and B is an array C such that C[i] is equal to the count of numbers that are present at or before the index i in both A and B.

Return the prefix common array of A and B.

A sequence of n integers is called a permutation if it contains all integers from 1 to n exactly once.

Example 1:

Input: A = [1,3,2,4], B = [3,1,2,4]

Output: [0,2,3,4]

Explanation: At i = 0: no number is common, so C[0] = 0.

At i = 1: 1 and 3 are common in A and B, so C[1] = 2.

At i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3.

At i = 3: 1, 2, 3, and 4 are common in A and B, so C[3] = 4.

Example 2:

Input: A = [2,3,1], B = [3,1,2]

Output: [0,1,3]

Explanation: At i = 0: no number is common, so C[0] = 0.

At i = 1: only 3 is common in A and B, so C[1] = 1.

At i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3.

Constraints:

  • 1 <= A.length == B.length == n <= 50
  • 1 <= A[i], B[i] <= n
  • It is guaranteed that A and B are both a permutation of n integers.

题目大意

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

解题思路

  1. 初始化：

    • 创建一个计数数组 count，用于记录每个数字在 A 和 B 中的出现次数。数组的长度为 n + 1（假设数组元素值的范围是 1 到 n）。
    • 创建变量 prefix，用于记录当前公共元素的数量。
    • 创建结果数组 res，用于存储每个索引的公共前缀结果。

  2. 迭代处理：

    • 遍历索引 i：
      • 将 A[i] 和 B[i] 的出现次数分别在 count 中加 1。
      • 如果 A[i] 的计数达到 2，说明 A[i] 是一个公共元素，增加 prefix。
      • 如果 B[i] 不等于 A[i] 且 B[i] 的计数达到 2，说明 B[i] 是另一个公共元素，增加 prefix。
      • 将当前的 prefix 值记录到 res[i]。

  3. 返回结果：

    • 最终返回结果数组 res。

复杂度分析

  • 时间复杂度：O(n)，遍历数组 A 和 B 一次。
  • 空间复杂度：O(n)，计数数组 count 的长度为 n + 1。

代码

/**
 * @param {number[]} A
 * @param {number[]} B
 * @return {number[]}
 */
var findThePrefixCommonArray = function (A, B) {
	const n = A.length;
	let prefix = 0;
	let count = new Array(n + 1).fill(0);
	let res = new Array(n);

	for (let i = 0; i < n; i++) {
		count[A[i]]++;
		count[B[i]]++;

		if (count[A[i]] === 2) {
			prefix++;
		}
		if (A[i] !== B[i] && count[B[i]] === 2) {
			prefix++;
		}
		res[i] = prefix;
	}
	return res;
};