目录

题目描述

输入描述

输出描述

用例

题目解析

算法源码

题目描述

给定两个数组a，b，若a[i] == b[j] 则称 [i, j] 为一个二元组，求在给定的两个数组中，二元组的个数。

输入描述

第一行输入 m
第二行输入m个数，表示第一个数组

第三行输入 n
第四行输入n个数，表示第二个数组

输出描述

二元组个数。

用例

题目解析

很简单的双重for，

/**** @param {Array} arrM 第二行输入的数组* @param {Number} m 第一行输入的数字m* @param {Array} arrN 第四行输入的数组* @param {Number} n 第二行输入的数字n* @returns*/
function getResult(arrM, m, arrN, n) {let count = 0;for (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {if (arrM[i] === arrN[j]) {count++;}}}return count;
}

但是不知道数量级多少，如果数量级比较大的话，则O(n*m)可能罩不住。

因此，我们还需要考虑下大数量级的情况。

我的思路如下：

先找找出m数组中，在n数组中出现的数及个数，在找出n数组中，在m数组中出现的数及个数，比如：

用例2中

countM = {2:2, 4:1}

countN = {2:2, 4:1}

然后将相同数的个数相乘，最后求和即为题解，比如2*2 + 1*1 = 5

算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});const lines = [];
rl.on("line", (line) => {lines.push(line);if (lines.length === 4) {const m = lines[0] - 0;const arrM = lines[1].split(" ").map(Number);const n = lines[2] - 0;const arrN = lines[3].split(" ").map(Number);console.log(getResult(arrM, m, arrN, n));lines.length = 0;}
});function getResult(arrM, m, arrN, n) {const setM = new Set(arrM);const setN = new Set(arrN);const countM = {};for (let m of arrM) {if (setN.has(m)) countM[m] ? countM[m]++ : (countM[m] = 1);}const countN = {};for (let n of arrN) {if (setM.has(n)) countN[n] ? countN[n]++ : (countN[n] = 1);}let count = 0;for (let k in countM) {count += countM[k] * countN[k];}return count;
}