【2024年华为OD机试】 (A卷,100分)- 二元组个数（Java JS PythonC/C++）

在这里插入图片描述

一、问题描述

以下是题目描述的 Markdown 格式：

题目描述

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

输入描述

第一行输入 m，表示第一个数组的长度。
第二行输入 m 个数，表示第一个数组 a。
第三行输入 n，表示第二个数组的长度。
第四行输入 n 个数，表示第二个数组 b。

输出描述

输出二元组的个数。

用例

用例 1

输入

输出

说明
二元组个数为 1 个。

用例 2

输入

6
1 1 2 2 4 5
3
2 2 4

输出

说明
二元组个数为 5 个。

代码实现思路

输入处理：
- 读取两个数组的长度 m 和 n。
- 读取两个数组 a 和 b。
统计二元组：
- 遍历数组 a 和 b，统计满足 a[i] == b[j] 的二元组个数。
输出结果：
- 输出统计结果。

题目解析

题目要求计算两个数组 arrM 和 arrN 中相同元素的出现次数的乘积之和。具体来说，对于每个在 arrM 中出现的元素，如果它也在 arrN 中出现，则计算它在两个数组中出现次数的乘积，并将这些乘积相加。

问题分析

暴力解法：
- 使用双重 for 循环遍历 arrM 和 arrN，统计相同元素的出现次数。
- 时间复杂度为 O(m * n)，其中 m 和 n 分别是 arrM 和 arrN 的长度。
- 这种方法在 m 和 n 较大时效率较低。
优化解法：
- 使用哈希表（字典）分别统计 arrM 和 arrN 中每个元素的出现次数。
- 然后遍历其中一个哈希表，计算相同元素的出现次数的乘积，并将这些乘积相加。
- 时间复杂度为 O(m + n)，空间复杂度为 O(m + n)。

优化解法详细步骤

统计 arrM 中每个元素的出现次数：
- 使用一个哈希表 countM，键为元素，值为该元素在 arrM 中出现的次数。
统计 arrN 中每个元素的出现次数：
- 使用一个哈希表 countN，键为元素，值为该元素在 arrN 中出现的次数。
计算相同元素的出现次数的乘积：
- 遍历 countM，对于每个键 key，如果 key 也在 countN 中出现，则计算 countM[key] * countN[key]，并将结果累加到 count 中。

二、JavaScript算法源码

以下是带有详细中文注释和逻辑讲解的 JavaScript 代码：

代码实现

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");// 创建 readline 接口，用于从控制台读取输入
const rl = readline.createInterface({input: process.stdin,  // 输入流为标准输入output: process.stdout, // 输出流为标准输出
});// 存储输入的行数据
const lines = [];// 监听 'line' 事件，每次读取一行输入
rl.on("line", (line) => {lines.push(line); // 将输入的行数据存入 lines 数组// 当 lines 数组中有 4 行数据时，表示输入完成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 数组，以便处理下一组输入lines.length = 0;}
});/*** 计算二元组个数的函数* @param {number[]} arrM 第一个数组* @param {number} m 第一个数组的长度* @param {number[]} arrN 第二个数组* @param {number} n 第二个数组的长度* @returns {number} 二元组的个数*/
function getResult(arrM, m, arrN, n) {// 使用 Set 数据结构存储两个数组的元素，方便快速查找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) {// 对于每个共同元素，其二元组个数为 countM[k] * countN[k]count += countM[k] * countN[k];}// 返回二元组的总数return count;
}

代码讲解

1. 输入处理

使用 readline 模块从控制台读取输入。
将输入的行数据存储在 lines 数组中。
当 lines 数组中有 4 行数据时，表示输入完成，开始解析数据：
- 第一行：第一个数组的长度 m。
- 第二行：第一个数组 arrM。
- 第三行：第二个数组的长度 n。
- 第四行：第二个数组 arrN。

2. 算法逻辑：`getResult` 函数

步骤 1：使用 Set 存储数组元素
- 将两个数组 arrM 和 arrN 转换为 Set 集合 setM 和 setN，方便快速查找。
步骤 2：统计共同元素的出现次数
- 遍历 arrM，统计每个元素在 arrN 中出现的次数，结果存储在 countM 对象中。
- 遍历 arrN，统计每个元素在 arrM 中出现的次数，结果存储在 countN 对象中。
步骤 3：计算二元组总数
- 对于每个共同元素 k，其二元组个数为 countM[k] * countN[k]。
- 将所有共同元素的二元组个数累加，得到总数 count。
步骤 4：返回结果
- 返回二元组的总数 count。

示例解析

输入

6
1 1 2 2 4 5
3
2 2 4

运行结果

解析：
- 共同元素为 2 和 4。
- 在 arrM 中：
  - 2 出现 2 次。
  - 4 出现 1 次。
- 在 arrN 中：
  - 2 出现 2 次。
  - 4 出现 1 次。
- 二元组总数：
  - 2 的二元组个数：2 * 2 = 4。
  - 4 的二元组个数：1 * 1 = 1。
  - 总数为 4 + 1 = 5。

总结

该代码通过 Set 和哈希表（对象）高效地统计了共同元素的出现次数。
时间复杂度为 O(m + n)，空间复杂度为 O(m + n)，适用于处理大规模数据。
代码逻辑清晰，注释详细，易于理解和扩展。

如果有其他问题，欢迎随时提问！

三、Java算法源码

以下是带有详细中文注释和逻辑讲解的 Java 代码：

代码实现

import java.util.*;
import java.util.stream.Collectors;public class Main {public static void main(String[] args) {// 创建 Scanner 对象，用于从控制台读取输入Scanner sc = new Scanner(System.in);// 读取第一个数组的长度 mint m = Integer.parseInt(sc.nextLine());// 读取第一个数组，并将其转换为 List<Integer>List<Integer> listM =Arrays.stream(sc.nextLine().split(" ")) // 按空格分割字符串.map(Integer::parseInt)          // 将字符串转换为整数.collect(Collectors.toList());   // 收集为 List// 读取第二个数组的长度 nint n = Integer.parseInt(sc.nextLine());// 读取第二个数组，并将其转换为 List<Integer>List<Integer> listN =Arrays.stream(sc.nextLine().split(" ")) // 按空格分割字符串.map(Integer::parseInt)          // 将字符串转换为整数.collect(Collectors.toList());   // 收集为 List// 调用算法函数，计算二元组个数并输出结果System.out.println(getResult(listM, listN));}/*** 计算二元组个数的函数* @param listM 第一个数组* @param listN 第二个数组* @return 二元组的个数*/public static int getResult(List<Integer> listM, List<Integer> listN) {// 使用 HashSet 存储两个数组的元素，方便快速查找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)) { // 如果第二个数组中包含当前元素// 使用 getOrDefault 方法统计该元素的出现次数countM.put(m, countM.getOrDefault(m, 0) + 1);}}// 统计第二个数组中每个元素在第一个数组中出现的次数HashMap<Integer, Integer> countN = new HashMap<>();for (Integer n : listN) {if (setM.contains(n)) { // 如果第一个数组中包含当前元素// 使用 getOrDefault 方法统计该元素的出现次数countN.put(n, countN.getOrDefault(n, 0) + 1);}}// 计算二元组的总数int count = 0;for (Integer k : countM.keySet()) {// 对于每个共同元素，其二元组个数为 countM.get(k) * countN.get(k)count += countM.get(k) * countN.get(k);}// 返回二元组的总数return count;}
}

代码讲解

1. 输入处理

使用 Scanner 从控制台读取输入。
读取第一个数组的长度 m 和数组内容，并将其转换为 List<Integer>。
读取第二个数组的长度 n 和数组内容，并将其转换为 List<Integer>。

2. 算法逻辑：`getResult` 函数

步骤 1：使用 HashSet 存储数组元素
- 将两个数组 listM 和 listN 转换为 HashSet 集合 setM 和 setN，方便快速查找。
步骤 2：统计共同元素的出现次数
- 遍历 listM，统计每个元素在 listN 中出现的次数，结果存储在 countM 哈希表中。
- 遍历 listN，统计每个元素在 listM 中出现的次数，结果存储在 countN 哈希表中。
步骤 3：计算二元组总数
- 对于每个共同元素 k，其二元组个数为 countM.get(k) * countN.get(k)。
- 将所有共同元素的二元组个数累加，得到总数 count。
步骤 4：返回结果
- 返回二元组的总数 count。

示例解析

输入

6
1 1 2 2 4 5
3
2 2 4

运行结果

解析：
- 共同元素为 2 和 4。
- 在 listM 中：
  - 2 出现 2 次。
  - 4 出现 1 次。
- 在 listN 中：
  - 2 出现 2 次。
  - 4 出现 1 次。
- 二元组总数：
  - 2 的二元组个数：2 * 2 = 4。
  - 4 的二元组个数：1 * 1 = 1。
  - 总数为 4 + 1 = 5。

总结

该代码通过 HashSet 和 HashMap 高效地统计了共同元素的出现次数。
时间复杂度为 O(m + n)，空间复杂度为 O(m + n)，适用于处理大规模数据。
代码逻辑清晰，注释详细，易于理解和扩展。

如果有其他问题，欢迎随时提问！

四、Python算法源码

以下是带有详细中文注释和逻辑讲解的 Python 代码：

代码实现

# 输入获取
# 读取第一个数组的长度 m
m = int(input())
# 读取第一个数组，并将其转换为整数列表
arrM = list(map(int, input().split()))# 读取第二个数组的长度 n
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  # 初始化计数为 1else:countM[m] += 1  # 否则计数加 1# 统计第二个数组中每个元素在第一个数组中出现的次数countN = {}for n in arrN:if n in setM:  # 如果第一个数组中包含当前元素if countN.get(n) is None:  # 如果该元素还未被统计过countN[n] = 1  # 初始化计数为 1else:countN[n] += 1  # 否则计数加 1# 计算二元组的总数count = 0for k in countM.keys():  # 遍历所有共同元素# 对于每个共同元素，其二元组个数为 countM[k] * countN[k]count += countM[k] * countN[k]# 返回二元组的总数return count# 算法调用
print(getResult(arrM, arrN))

代码讲解

1. 输入处理

使用 input() 函数从控制台读取输入。
读取第一个数组的长度 m 和数组内容，并将其转换为整数列表 arrM。
读取第二个数组的长度 n 和数组内容，并将其转换为整数列表 arrN。

2. 算法逻辑：`getResult` 函数

步骤 1：使用集合存储数组元素
- 将两个数组 arrM 和 arrN 转换为集合 setM 和 setN，方便快速查找。
步骤 2：统计共同元素的出现次数
- 遍历 arrM，统计每个元素在 arrN 中出现的次数，结果存储在字典 countM 中。
- 遍历 arrN，统计每个元素在 arrM 中出现的次数，结果存储在字典 countN 中。
步骤 3：计算二元组总数
- 对于每个共同元素 k，其二元组个数为 countM[k] * countN[k]。
- 将所有共同元素的二元组个数累加，得到总数 count。
步骤 4：返回结果
- 返回二元组的总数 count。

示例解析

输入

6
1 1 2 2 4 5
3
2 2 4

运行结果

解析：
- 共同元素为 2 和 4。
- 在 arrM 中：
  - 2 出现 2 次。
  - 4 出现 1 次。
- 在 arrN 中：
  - 2 出现 2 次。
  - 4 出现 1 次。
- 二元组总数：
  - 2 的二元组个数：2 * 2 = 4。
  - 4 的二元组个数：1 * 1 = 1。
  - 总数为 4 + 1 = 5。

总结

该代码通过集合和字典高效地统计了共同元素的出现次数。
时间复杂度为 O(m + n)，空间复杂度为 O(m + n)，适用于处理大规模数据。
代码逻辑清晰，注释详细，易于理解和扩展。

如果有其他问题，欢迎随时提问！

五、C/C++算法源码：

以下是C++ 实现，并附有详细的中文注释和逻辑讲解：

C++ 代码实现

#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>using namespace std;/*** 计算二元组个数的函数* @param arrM 第一个数组* @param arrN 第二个数组* @return 二元组的个数*/
int getResult(const vector<int>& arrM, const vector<int>& arrN) {// 使用 unordered_set 存储两个数组的元素，方便快速查找unordered_set<int> setM(arrM.begin(), arrM.end()); // 第一个数组的元素集合unordered_set<int> setN(arrN.begin(), arrN.end()); // 第二个数组的元素集合// 统计第一个数组中每个元素在第二个数组中出现的次数unordered_map<int, int> countM;for (int m : arrM) {if (setN.count(m)) { // 如果第二个数组中包含当前元素countM[m]++; // 统计该元素的出现次数}}// 统计第二个数组中每个元素在第一个数组中出现的次数unordered_map<int, int> countN;for (int n : arrN) {if (setM.count(n)) { // 如果第一个数组中包含当前元素countN[n]++; // 统计该元素的出现次数}}// 计算二元组的总数int count = 0;for (const auto& pair : countM) {int k = pair.first; // 共同元素// 对于每个共同元素，其二元组个数为 countM[k] * countN[k]count += pair.second * countN[k];}// 返回二元组的总数return count;
}int main() {// 读取第一个数组的长度 mint m;cin >> m;// 读取第一个数组vector<int> arrM(m);for (int i = 0; i < m; i++) {cin >> arrM[i];}// 读取第二个数组的长度 nint n;cin >> n;// 读取第二个数组vector<int> arrN(n);for (int i = 0; i < n; i++) {cin >> arrN[i];}// 调用算法函数，计算二元组个数并输出结果cout << getResult(arrM, arrN) << endl;return 0;
}

代码讲解

1. 输入处理

使用 cin 从标准输入读取数据。
读取第一个数组的长度 m 和数组内容，并将其存储在 vector<int> arrM 中。
读取第二个数组的长度 n 和数组内容，并将其存储在 vector<int> arrN 中。

2. 算法逻辑：`getResult` 函数

步骤 1：使用 unordered_set 存储数组元素
- 将两个数组 arrM 和 arrN 转换为 unordered_set 集合 setM 和 setN，方便快速查找。
步骤 2：统计共同元素的出现次数
- 遍历 arrM，统计每个元素在 arrN 中出现的次数，结果存储在 unordered_map<int, int> countM 中。
- 遍历 arrN，统计每个元素在 arrM 中出现的次数，结果存储在 unordered_map<int, int> countN 中。
步骤 3：计算二元组总数
- 对于每个共同元素 k，其二元组个数为 countM[k] * countN[k]。
- 将所有共同元素的二元组个数累加，得到总数 count。
步骤 4：返回结果
- 返回二元组的总数 count。

示例解析

输入

6
1 1 2 2 4 5
3
2 2 4

运行结果

解析：
- 共同元素为 2 和 4。
- 在 arrM 中：
  - 2 出现 2 次。
  - 4 出现 1 次。
- 在 arrN 中：
  - 2 出现 2 次。
  - 4 出现 1 次。
- 二元组总数：
  - 2 的二元组个数：2 * 2 = 4。
  - 4 的二元组个数：1 * 1 = 1。
  - 总数为 4 + 1 = 5。