(100分)- 二元组个数（Java JS Python）

(100分)- 二元组个数（Java & JS & Python）

题目描述

给定两个数组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)的时间复杂度可能无法满足要求。

针对这个问题，我的解决方案如下：

1. 首先统计m数组中每个数字在n数组中出现的次数
2. 同时统计n数组中每个数字在m数组中出现的次数
3. 将两个统计结果中相同数字的出现次数相乘
4. 最后将所有乘积相加得到最终结果

以示例2为例：

• m数组统计结果：{2:2, 4:1}
• n数组统计结果：{2:2, 4:1}
• 计算结果：22 + 11 = 5

JavaScript算法源码

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

Java算法源码

import java.util.*; import java.util.stream.Collectors; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m = Integer.parseInt(sc.nextLine()); List<Integer> listM = Arrays.stream(sc.nextLine().split(" ")).map(Integer::parseInt).collect(Collectors.toList()); int n = Integer.parseInt(sc.nextLine()); List<Integer> listN = Arrays.stream(sc.nextLine().split(" ")).map(Integer::parseInt).collect(Collectors.toList()); System.out.println(getResult(listM, listN)); } public static int getResult(List<Integer> listM, List<Integer> listN) { HashSet<Integer> setM = new HashSet<Integer>(listM); HashSet<Integer> setN = new HashSet<Integer>(listN); HashMap<Integer, Integer> countM = new HashMap<>(); for (Integer m : listM) { if (setN.contains(m)) { countM.put(m, countM.getOrDefault(m, 0) + 1); } } HashMap<Integer, Integer> countN = new HashMap<>(); for (Integer n : listN) { if (setM.contains(n)) { countN.put(n, countN.getOrDefault(n, 0) + 1); } } int count = 0; for (Integer k : countM.keySet()) { count += countM.get(k) * countN.get(k); } return count; } }

Python算法源码

# 输入获取 m = int(input()) arrM = list(map(int, input().split())) n = int(input()) arrN = list(map(int, input().split())) # 算法入口 def getResult(arrM, arrN): setM = set(arrM) setN = set(arrN) countM = {} for m in arrM: if m in setN: if countM.get(m) is None: countM[m] = 1 else: countM[m] += 1 countN = {} for n in arrN: if n in setM: if countN.get(n) is None: countN[n] = 1 else: countN[n] += 1 count = 0 for k in countM.keys(): count += countM[k] * countN[k] return count # 算法调用 print(getResult(arrM, arrN))