Skip to content

Latest commit

 

History

History
159 lines (123 loc) · 4.71 KB

2657.md

File metadata and controls

159 lines (123 loc) · 4.71 KB
title description keywords
2657. 找到两个数组的前缀公共数组
LeetCode 2657. 找到两个数组的前缀公共数组题解，Find the Prefix Common Array of Two Arrays，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。
LeetCode
2657. 找到两个数组的前缀公共数组
找到两个数组的前缀公共数组
Find the Prefix Common Array of Two Arrays
解题思路
位运算
数组
哈希表

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

🟠 Medium  🔖  位运算 数组 哈希表  🔗 力扣 LeetCode

题目

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;
};