2657. 找到两个数组的前缀公共数组 - 力扣（LeetCode）
2657. 找到两个数组的前缀公共数组 - 给你两个下标从 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 =...
思路
Hash记录出现过的数值，如果再次出现则公共值增1。
代码
class Solution {
public int[] findThePrefixCommonArray(int[] A, int[] B) {
int n = A.length;
// 记录遇到数值的数量
int[] set = new int[n + 1];
int[] ans = new int[n];
int total = 0;
for (int i = 0; i < n; i++) {
if (A[i] == B[i]) {
// 如果相等可以忽略计数
ans[i] = ++total;
} else {
// 如果不相等，需要分别计数
total += set[A[i]]++;
total += set[B[i]]++;
ans[i] = total;
}
}
return ans;
}
}
1 个帖子 - 1 位参与者
来源: LinuxDo 最新话题查看原文