当前位置：首页 > news >正文

统计匹配的二元组个数 - 华为OD机试真题(A卷、JavaScript题解)

news 2025/5/10 3:29:19

华为OD机试题库《C++》限时优惠 9.9

华为OD机试题库《Python》限时优惠 9.9

华为OD机试题库《JavaScript》限时优惠 9.9

针对刷题难，效率慢，我们提供一对一算法辅导，针对个人情况定制化的提高计划（全称1V1效率更高）。

看不懂有疑问需要答疑辅导欢迎私VX： code5bug

题目描述

给定两个数组A和B，若数组A的某个元素A[i]与数组B中某个元素B[j] 满足 A[i]==B[j]，则寻找到一个值匹配的二元组 (i,j)。请统计在这两个数组A和B中，一共存在多少个这样的二元组。

输入描述

第一行输入数组A的长度M
第二行输入数组B的长度N
第三行输入数组A的值（空格分隔）
第四行输入数组B的值（空格分隔）

备注：

若不存在相等的值，则输出0。
所采用的算法复杂度需小于 O(N2)，否则会超时。
输入数组中允许出现重复数字，一个数字可以匹配多次。

输出描述

输出匹配的二元组个数。

示例1

示例2

输入：
6
3
1 2 4 4 2 1
1 2 3输出：
4

示例3

输入：
4
1
1 2 3 4
1输出：
1

示例4

输入：
6
3
1 1 2 2 4 5
2 2 4输出：
5

题解

统计频次：首先统计数组B中每个数字出现的次数。
遍历匹配：遍历数组A，对于每个元素，检查中是否存在该数字。如果存在，则将该数字的频率累加到结果中。
复杂度分析：统计频次的时间复杂度为O(N)，遍历匹配的时间复杂度为O(M)，总时间复杂度为O(M + N)，满足题目要求的小于O(N^2)的复杂度。

JavaScript

const rl = require('readline').createInterface({input: process.stdin,output: process.stdout,
});
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;// Author: code5bug
(async () => {const M = parseInt(await readline());const N = parseInt(await readline());const A = (await readline()).split(' ').map(Number);const B = (await readline()).split(' ').map(Number);// 统计数组B中每个数字出现的频率const freq = {};for (const num of B) {freq[num] = (freq[num] || 0) + 1;}let count = 0;// 遍历数组A，统计匹配的二元组个数for (const num of A) {if (freq[num] !== undefined) {count += freq[num];}}console.log(count);rl.close();
})();