公主岭网站开发,dw网站首页制作,免费微商城平台官网,马鞍山人才网2025 A卷 100分 题型 本文涵盖详细的问题分析、解题思路、代码实现、代码详解、测试用例以及综合分析#xff1b; 并提供Java、python、JavaScript、C、C语言、GO六种语言的最佳实现方式#xff01; 2025华为OD真题目录全流程解析/备考攻略/经验分享 华为OD机试真题《统计匹配… 2025 A卷 100分 题型 本文涵盖详细的问题分析、解题思路、代码实现、代码详解、测试用例以及综合分析 并提供Java、python、JavaScript、C、C语言、GO六种语言的最佳实现方式 2025华为OD真题目录全流程解析/备考攻略/经验分享 华为OD机试真题《统计匹配的二元组个数》 目录 题目名称统计匹配的二元组个数题目描述 Java问题分析解题思路代码实现代码详细解析示例测试综合分析 python问题分析解题思路代码实现代码详细解析示例测试综合分析 JavaScript问题分析解题思路代码实现代码详细解析示例测试综合分析 C问题分析解题思路代码实现代码逐行解析示例测试综合分析 C语言问题分析解题思路代码实现代码详细解析示例测试综合分析 GO问题分析解题思路代码实现代码详细解析示例测试综合分析 更多内容 题目名称统计匹配的二元组个数 知识点数组、哈希表 时间限制1秒 空间限制32MB 限定语言不限 题目描述
给定两个数组A和B统计满足A[i] B[j]的二元组(i,j)的总个数。
输入描述
第一行输入数组A的长度M第二行输入数组B的长度N第三行输入数组A的元素空格分隔第四行输入数组B的元素空格分隔
输出描述 输出匹配的二元组个数。若不存在匹配输出0。
示例1 输入
5
4
1 2 3 4 5
4 3 2 1 输出
4 示例2 输入
6
3
1 2 4 4 2 1
1 2 3 输出
4 Java
问题分析
我们需要统计两个数组A和B中满足A[i] B[j]的二元组(i,j)的总个数。直接遍历所有可能的组合会导致时间复杂度为O(M*N)但通过哈希表优化可以将时间复杂度降低到O(M N)。 解题思路
哈希表统计频率遍历数组A用哈希表记录每个元素出现的次数。遍历数组B匹配遍历数组B对于每个元素在哈希表中查找其出现次数并累加。 代码实现
import java.util.*;
import java.io.*;public class Main {public static void main(String[] args) throws IOException {// 使用BufferedReader读取输入避免Scanner的换行符问题BufferedReader br new BufferedReader(new InputStreamReader(System.in));// 读取数组A和B的长度int M Integer.parseInt(br.readLine());int N Integer.parseInt(br.readLine());// 读取数组A的元素并转换为整型数组String[] aParts br.readLine().split( );int[] a new int[M];for (int i 0; i M; i) {a[i] Integer.parseInt(aParts[i]);}// 读取数组B的元素并转换为整型数组String[] bParts br.readLine().split( );int[] b new int[N];for (int i 0; i N; i) {b[i] Integer.parseInt(bParts[i]);}// 创建哈希表统计数组A中每个元素的出现次数MapInteger, Integer countMap new HashMap();for (int num : a) {countMap.put(num, countMap.getOrDefault(num, 0) 1);}// 遍历数组B累加匹配次数int result 0;for (int num : b) {result countMap.getOrDefault(num, 0);}// 输出结果System.out.println(result);}
}代码详细解析 读取输入 BufferedReader逐行读取输入避免Scanner的换行符问题。前两行读取数组A和B的长度M和N。第三行读取数组A的元素并转换为整型数组。第四行读取数组B的元素并转换为整型数组。 统计数组A的元素频率 使用HashMap存储数组A中每个元素及其出现次数。countMap.getOrDefault(num, 0)确保元素不存在时返回0。 遍历数组B计算匹配次数 对数组B中的每个元素查找其在哈希表中的出现次数。累加所有匹配次数得到最终结果。 示例测试
示例1输入
5
4
1 2 3 4 5
4 3 2 1输出
4解析
数组A中每个元素出现1次数组B中的元素4、3、2、1均能在A中找到总共有4对。
示例2输入
6
3
1 2 4 4 2 1
1 2 3输出
4解析
数组A中1出现2次、2出现2次数组B中的1和2分别匹配2次总共有4次。 综合分析 时间复杂度 统计频率O(M)遍历数组A一次。匹配计算O(N)遍历数组B一次。总复杂度O(M N)线性时间复杂度。 空间复杂度 哈希表存储O(M)存储数组A中所有不同元素及其频率。 优势 高效性相比暴力法的O(M*N)哈希表将复杂度优化到O(M N)。代码简洁逻辑清晰易于理解和维护。 适用场景 处理大规模数据时哈希表方法能显著提升性能。适用于需要快速查找元素出现次数的场景。 python
问题分析
我们需要统计两个数组A和B中满足A[i] B[j]的二元组(i,j)的总个数。直接遍历所有可能的组合会导致时间复杂度为O(M*N)但通过哈希表优化可以将时间复杂度降低到O(M N)。 解题思路
哈希表统计频率遍历数组A用字典记录每个元素出现的次数。遍历数组B匹配遍历数组B对于每个元素在字典中查找其出现次数并累加。 代码实现
def main():import sys# 读取输入数据m int(sys.stdin.readline()) # 读取数组A的长度n int(sys.stdin.readline()) # 读取数组B的长度# 读取数组A的元素并转换为整数列表a list(map(int, sys.stdin.readline().split()))# 验证数组长度是否匹配输入值if len(a) ! m:print(0)return# 读取数组B的元素并转换为整数列表b list(map(int, sys.stdin.readline().split()))# 验证数组长度是否匹配输入值if len(b) ! n:print(0)return# 创建字典统计数组A中每个元素的出现次数count_dict {}for num in a:# 如果元素存在计数1不存在则初始化为0后1count_dict[num] count_dict.get(num, 0) 1# 遍历数组B统计总匹配次数total 0for num in b:# 从字典中获取该元素的出现次数默认0次total count_dict.get(num, 0)print(total)if __name__ __main__:main()代码详细解析 输入处理 sys.stdin.readline() 逐行读取输入避免缓冲区问题m 和 n 分别读取数组A和B的长度a list(map(...)) 将输入行分割为字符串列表并转换为整数列表验证数组长度是否与输入值一致防止数据错误 频率统计字典 创建空字典 count_dict 存储元素频率count_dict.get(num, 0) 是字典的安全访问方法 当元素存在时返回当前计数值不存在时返回默认值0 遍历数组A时每个元素计数1 匹配计算 遍历数组B的每个元素count_dict.get(num, 0) 获取该元素在A中的出现次数所有匹配次数累加到total 边界处理 数组长度验证防止数据格式错误不存在的元素自动按0次处理 示例测试
示例1输入
5
4
1 2 3 4 5
4 3 2 1输出
4解析
A中每个元素出现1次B中的4、3、2、1均能在A中找到总匹配次数 1111 4
示例2输入
6
3
1 2 4 4 2 1
1 2 3输出
4解析
A中1出现2次2出现2次4出现2次B中的1匹配2次2匹配2次3匹配0次总匹配次数 220 4 综合分析 时间复杂度 统计频率O(M)遍历数组A一次匹配计算O(N)遍历数组B一次总复杂度O(M N)线性时间复杂度 空间复杂度 字典存储最差O(M)所有元素不同时输入存储O(M N) 存储两个数组 性能优势 相比暴力法的O(M*N)效率提升数百倍例如当MN105时暴力法需1010次运算不可行而哈希法仅需2*10^5次 适用场景 大规模数据处理如M1e6, N1e6需要频繁查询元素出现次数的场景元素取值范围较大的情况哈希表不依赖连续空间 Python特性利用 字典的get()方法简化了存在性检查默认值逻辑map()函数高效处理类型转换动态列表自动处理变长数据 扩展性 支持非整数类型只需可哈希可轻松修改为统计三元组、四元组等适用于分布式计算分块统计频率后合并 JavaScript
问题分析
我们需要统计两个数组 A 和 B 中满足 A[i] B[j] 的二元组 (i, j) 的总个数。直接遍历所有组合的时间复杂度为 O(M*N)但通过哈希表优化可以将时间复杂度降低到 O(M N)。 解题思路
哈希表统计频率遍历数组 A用哈希表记录每个元素出现的次数。遍历数组 B 匹配遍历数组 B对于每个元素在哈希表中查找其出现次数并累加。 代码实现
const readline require(readline);const rl readline.createInterface({input: process.stdin,output: process.stdout,terminal: false
});// 输入处理逻辑
let lineCount 0;
let M, N, A, B;rl.on(line, (line) {switch (lineCount) {case 0: // 读取数组A的长度MM parseInt(line.trim());break;case 1: // 读取数组B的长度NN parseInt(line.trim());break;case 2: // 读取数组A的元素A line.trim().split(/\s/).map(Number);if (A.length ! M) {console.log(0);process.exit();}break;case 3: // 读取数组B的元素B line.trim().split(/\s/).map(Number);if (B.length ! N) {console.log(0);process.exit();}processInput(); // 处理输入数据break;}lineCount;
});function processInput() {// 统计A中元素的频率const countMap {};for (const num of A) {countMap[num] (countMap[num] || 0) 1;}// 计算总匹配次数let total 0;for (const num of B) {total countMap[num] || 0;}console.log(total);rl.close();
}代码详细解析 输入处理 const rl readline.createInterface(...) // 创建输入接口
rl.on(line, ...) // 监听每一行输入使用 Node.js 的 readline 模块逐行读取输入通过 switch 语句处理不同行的输入内容 数组验证 if (A.length ! M) { ... } // 验证数组A长度
if (B.length ! N) { ... } // 验证数组B长度检查输入数组长度是否与声明的长度一致发现不一致立即输出 0 并退出 哈希表统计 const countMap {};
for (const num of A) {countMap[num] (countMap[num] || 0) 1;
}使用普通对象作为哈希表(countMap[num] || 0) 实现类似 Python 的 get() 方法 匹配计算 for (const num of B) {total countMap[num] || 0;
}遍历数组 B 的每个元素累加哈希表中对应元素的出现次数 示例测试
示例1输入
5
4
1 2 3 4 5
4 3 2 1输出
4解析
A 中每个元素出现1次B 中的 4、3、2、1 均能在 A 中找到总匹配次数 1111 4
示例2输入
6
3
1 2 4 4 2 1
1 2 3输出
4解析
A 中 1 出现2次2 出现2次B 中的 1 匹配2次2 匹配2次总匹配次数 220 4 综合分析 时间复杂度 统计频率O(M)遍历数组A一次匹配计算O(N)遍历数组B一次总复杂度O(M N)线性时间复杂度 空间复杂度 哈希表存储最差 O(M)所有元素不同时输入存储O(M N) 存储两个数组 性能优势 相比暴力法 O(M*N) 的复杂度效率提升数百倍例如当 MN10^5 时暴力法需要 1e10 次运算不可行而哈希法仅需 2e5 次 JavaScript 特性利用 对象动态属性实现哈希表|| 运算符实现默认值map(Number) 快速类型转换 扩展性 支持非数字类型需可哈希可轻松修改为统计三元组等复杂场景适用于浏览器和 Node.js 双环境 C
问题分析
给定两个数组A和B统计满足A[i] B[j]的二元组(i,j)的总个数。直接遍历所有组合的时间复杂度为O(M*N)但通过哈希表优化可以将时间复杂度降低到O(M N)。 解题思路
哈希表统计频率遍历数组A用unordered_map记录每个元素出现的次数。遍历数组B匹配遍历数组B对于每个元素在哈希表中查找其出现次数并累加。 代码实现
#include iostream
#include vector
#include sstream
#include unordered_mapusing namespace std;int main() {int M, N;// 读取数组A和B的长度cin M N;// 清除输入缓冲区中的换行符cin.ignore(numeric_limitsstreamsize::max(), \n);// 读取数组A的元素string lineA;getline(cin, lineA);vectorint A;stringstream ssA(lineA);int num;while (ssA num) {A.push_back(num);}// 验证数组A长度if (A.size() ! M) {cout 0 endl;return 0;}// 读取数组B的元素string lineB;getline(cin, lineB);vectorint B;stringstream ssB(lineB);while (ssB num) {B.push_back(num);}// 验证数组B长度if (B.size() ! N) {cout 0 endl;return 0;}// 统计数组A中每个元素的出现次数unordered_mapint, int countMap;for (int num : A) {countMap[num];}// 遍历数组B统计总匹配次数int total 0;for (int num : B) {total countMap[num]; // 若不存在则返回0}cout total endl;return 0;
}代码逐行解析 输入处理 cin M N; // 读取数组A和B的长度
cin.ignore(...); // 清除缓冲区中的换行符
getline(cin, lineA); // 读取数组A的元素行使用cin读取数组长度后必须用cin.ignore()清除缓冲区残留的换行符getline按行读取数组元素避免空格和换行符干扰 数组元素解析 stringstream ssA(lineA); // 将字符串转换为流
while (ssA num) { ... } // 逐个读取整数stringstream将字符串按空格分割为整数流vector动态存储数组元素 哈希表统计 unordered_mapint, int countMap;
for (int num : A) { countMap[num]; }unordered_map以O(1)时间复杂度实现键值查找遍历数组A时每个元素在哈希表中计数1 匹配次数计算 total countMap[num]; // 若不存在则返回0直接通过countMap[num]访问次数未找到时返回0遍历数组B时累加所有匹配次数 示例测试
示例1输入
5 4
1 2 3 4 5
4 3 2 1输出
4解析
A中的每个元素出现1次B中的4、3、2、1均能在A中找到总匹配次数11114
示例2输入
6 3
1 2 4 4 2 1
1 2 3输出
4解析
A中1出现2次2出现2次B中的1匹配2次2匹配2次3匹配0次总匹配次数2204 综合分析 时间复杂度 统计频率O(M)遍历数组A一次匹配计算O(N)遍历数组B一次总复杂度O(M N)线性时间复杂度 空间复杂度 哈希表存储最差O(M)所有元素不同时输入存储O(M N) 存储两个数组 性能优势 相比暴力法的O(M*N)效率提升数百倍例如当MN10^5时暴力法需要1e10次运算不可行哈希法仅需2e5次 C特性利用 unordered_map实现哈希表平均O(1)查询时间stringstream处理复杂的输入分割逻辑vector动态数组自动管理内存 扩展性 支持非整型数据需自定义哈希函数可轻松修改为统计三元组等复杂场景适用于高性能计算场景如嵌入式系统 C语言
问题分析
我们需要统计两个数组A和B中满足A[i] B[j]的二元组(i,j)的总个数。直接遍历所有组合的时间复杂度为O(M*N)但通过哈希表优化可以将时间复杂度降低到O(M N)。 解题思路
哈希表统计频率遍历数组A使用哈希表记录每个元素出现的次数。遍历数组B匹配遍历数组B对于每个元素在哈希表中查找其出现次数并累加。 代码实现
#include stdio.h
#include stdlib.h
#include string.h
#include math.h#define HASH_SIZE 10007 // 哈希表大小质数减少冲突typedef struct HashNode {int key; // 存储元素值int value; // 存储出现次数struct HashNode *next;
} HashNode;typedef struct {HashNode **buckets; // 哈希桶数组int size; // 哈希表大小
} HashMap;// 创建哈希表
HashMap* createHashMap(int size) {HashMap *map (HashMap*)malloc(sizeof(HashMap));map-size size;map-buckets (HashNode**)calloc(size, sizeof(HashNode*)); // 初始化为空指针return map;
}// 插入元素到哈希表
void put(HashMap *map, int key) {int index abs(key) % map-size; // 哈希函数绝对值取模处理负数HashNode *current map-buckets[index];// 遍历链表查找是否已存在该键while (current ! NULL) {if (current-key key) {current-value; // 存在则计数加1return;}current current-next;}// 创建新节点插入链表头部HashNode *newNode (HashNode*)malloc(sizeof(HashNode));newNode-key key;newNode-value 1;newNode-next map-buckets[index];map-buckets[index] newNode;
}// 查询元素出现次数
int get(HashMap *map, int key) {int index abs(key) % map-size;HashNode *current map-buckets[index];// 遍历链表查找键while (current ! NULL) {if (current-key key) {return current-value;}current current-next;}return 0; // 未找到返回0
}// 释放哈希表内存
void freeHashMap(HashMap *map) {for (int i 0; i map-size; i) {HashNode *current map-buckets[i];while (current ! NULL) {HashNode *temp current;current current-next;free(temp);}}free(map-buckets);free(map);
}int main() {char line[1000000];int M, N;// 读取数组A和B的长度fgets(line, sizeof(line), stdin);sscanf(line, %d, M);fgets(line, sizeof(line), stdin);sscanf(line, %d, N);// 读取数组A的元素fgets(line, sizeof(line), stdin);int *A (int*)malloc(M * sizeof(int));int count 0;char *token strtok(line, );while (token ! NULL count M) {A[count] atoi(token);token strtok(NULL, );}if (count ! M) { // 验证元素数量是否正确printf(0\n);free(A);return 0;}// 读取数组B的元素fgets(line, sizeof(line), stdin);int *B (int*)malloc(N * sizeof(int));count 0;token strtok(line, );while (token ! NULL count N) {B[count] atoi(token);token strtok(NULL, );}if (count ! N) { // 验证元素数量是否正确printf(0\n);free(A);free(B);return 0;}// 创建哈希表并统计A的频次HashMap *map createHashMap(HASH_SIZE);for (int i 0; i M; i) {put(map, A[i]);}// 遍历B数组累加匹配次数int total 0;for (int i 0; i N; i) {total get(map, B[i]);}printf(%d\n, total);// 释放内存freeHashMap(map);free(A);free(B);return 0;
}代码详细解析 哈希表结构定义 HashNode链表节点存储键、值和下一个节点的指针。HashMap哈希表结构包含桶数组和大小。 哈希表操作 createHashMap分配内存初始化桶数组。put插入元素。若键存在计数加1否则新建节点插入链表头部。get查询键的出现次数遍历链表查找。freeHashMap释放哈希表所有节点内存。 输入处理 使用fgets逐行读取输入strtok分割字符串。验证数组长度是否与输入一致避免数据错误。 核心逻辑 遍历数组A通过哈希表统计频次。遍历数组B累加哈希表中的频次得到总匹配数。 示例测试
示例1输入
5
4
1 2 3 4 5
4 3 2 1输出
4解析
A中每个元素出现1次。B中4、3、2、1各匹配1次总对数4。
示例2输入
6
3
1 2 4 4 2 1
1 2 3输出
4解析
A中1出现2次2出现2次。B中1和2各匹配2次总对数4。 综合分析 时间复杂度 统计频率O(M)遍历数组A一次。匹配计算O(N)遍历数组B一次。总复杂度O(M N)线性时间复杂度。 空间复杂度 哈希表O(M)存储数组A元素的频次。输入数组O(M N)存储原始数据。 优势 高效性避免暴力法的O(M*N)复杂度。通用性支持任意整数包括负数哈希函数处理简单。 适用场景 大规模数据如M和N达到10^5级别。需要快速统计元素频次并匹配的场景。 GO
问题分析
给定两个数组A和B统计满足A[i] B[j]的二元组(i,j)的总个数。直接遍历所有组合的时间复杂度为O(M*N)但通过哈希表优化可以将时间复杂度降低到O(M N)。 解题思路
哈希表统计频率遍历数组A用map记录每个元素出现的次数。遍历数组B匹配遍历数组B对于每个元素在哈希表中查找其出现次数并累加。 代码实现
package mainimport (bufiofmtosstrconvstrings
)func main() {// 创建输入扫描器scanner : bufio.NewScanner(os.Stdin)// 读取数组A的长度Mscanner.Scan()M, _ : strconv.Atoi(scanner.Text())// 读取数组B的长度Nscanner.Scan()N, _ : strconv.Atoi(scanner.Text())// 读取数组A的元素scanner.Scan()aLine : scanner.Text()A : strings.Fields(aLine)if len(A) ! M {fmt.Println(0)return}// 读取数组B的元素scanner.Scan()bLine : scanner.Text()B : strings.Fields(bLine)if len(B) ! N {fmt.Println(0)return}// 统计数组A中元素的出现次数countMap : make(map[string]int)for _, numStr : range A {countMap[numStr]}// 计算总匹配次数total : 0for _, numStr : range B {total countMap[numStr]}fmt.Println(total)
}代码详细解析 输入处理 bufio.Scanner创建输入扫描器逐行读取数据。strconv.Atoi将字符串转换为整数用于读取数组长度。strings.Fields按空格分割字符串处理数组元素。 数组验证 if len(A) ! M { ... } // 验证数组A长度
if len(B) ! N { ... } // 验证数组B长度检查分割后的元素数量是否与声明的长度一致。 哈希表统计 countMap : make(map[string]int)
for _, numStr : range A {countMap[numStr]
}使用字符串直接作为键避免类型转换开销。遍历数组A时每个字符串元素计数1。 匹配计算 for _, numStr : range B {total countMap[numStr]
}遍历数组B的每个元素累加哈希表中的出现次数。未找到时返回默认值0。 示例测试
示例1输入
5
4
1 2 3 4 5
4 3 2 1输出
4解析
A中每个元素出现1次。B中的4、3、2、1均匹配1次总对数4。
示例2输入
6
3
1 2 4 4 2 1
1 2 3输出
4解析
A中1出现2次2出现2次。B中的1匹配2次2匹配2次总对数4。 综合分析 时间复杂度 统计频率O(M)遍历数组A一次。匹配计算O(N)遍历数组B一次。总复杂度O(M N)线性时间复杂度。 空间复杂度 哈希表存储O(M)存储数组A元素的字符串形式。输入存储O(M N)存储原始字符串数据。 性能优化 直接使用字符串键避免多次类型转换。哈希表快速查找Go的map实现基于哈希表平均O(1)查询时间。 适用场景 适用于大规模数据如M1e6, N1e6。需要快速统计元素出现次数的场景。元素包含非数字字符的场景如apple。 扩展性 支持任意可哈希类型如结构体。可轻松修改为统计三元组、四元组等。 更多内容
https://www.kdocs.cn/l/cvk0eoGYucWA
本文发表于【纪元A梦】关注我获取更多实用教程/资源
