您的位置:首页 > 教育 > 培训 > 摄影设计说明_网络工程可以从事什么工作_网站批量查询工具_java培训机构

摄影设计说明_网络工程可以从事什么工作_网站批量查询工具_java培训机构

2025/4/22 2:12:28 来源:https://blog.csdn.net/sinat_26368147/article/details/147259253  浏览:    关键词:摄影设计说明_网络工程可以从事什么工作_网站批量查询工具_java培训机构
摄影设计说明_网络工程可以从事什么工作_网站批量查询工具_java培训机构

在这里插入图片描述

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)。


解题思路

  1. 哈希表统计频率:遍历数组A,用哈希表记录每个元素出现的次数。
  2. 遍历数组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中每个元素的出现次数Map<Integer, 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);}
}

代码详细解析

  1. 读取输入

    • BufferedReader逐行读取输入,避免Scanner的换行符问题。
    • 前两行读取数组A和B的长度MN
    • 第三行读取数组A的元素并转换为整型数组。
    • 第四行读取数组B的元素并转换为整型数组。
  2. 统计数组A的元素频率

    • 使用HashMap存储数组A中每个元素及其出现次数。
    • countMap.getOrDefault(num, 0)确保元素不存在时返回0。
  3. 遍历数组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次。

综合分析

  1. 时间复杂度

    • 统计频率:O(M),遍历数组A一次。
    • 匹配计算:O(N),遍历数组B一次。
    • 总复杂度:O(M + N),线性时间复杂度。
  2. 空间复杂度

    • 哈希表存储:O(M),存储数组A中所有不同元素及其频率。
  3. 优势

    • 高效性:相比暴力法的O(M*N),哈希表将复杂度优化到O(M + N)。
    • 代码简洁:逻辑清晰,易于理解和维护。
  4. 适用场景

    • 处理大规模数据时,哈希表方法能显著提升性能。
    • 适用于需要快速查找元素出现次数的场景。

python

问题分析

我们需要统计两个数组A和B中满足A[i] == B[j]的二元组(i,j)的总个数。直接遍历所有可能的组合会导致时间复杂度为O(M*N),但通过哈希表优化可以将时间复杂度降低到O(M + N)。


解题思路

  1. 哈希表统计频率:遍历数组A,用字典记录每个元素出现的次数。
  2. 遍历数组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()

代码详细解析

  1. 输入处理

    • sys.stdin.readline() 逐行读取输入,避免缓冲区问题
    • mn 分别读取数组A和B的长度
    • a = list(map(...)) 将输入行分割为字符串列表并转换为整数列表
    • 验证数组长度是否与输入值一致,防止数据错误
  2. 频率统计字典

    • 创建空字典 count_dict 存储元素频率
    • count_dict.get(num, 0) 是字典的安全访问方法:
      • 当元素存在时返回当前计数值
      • 不存在时返回默认值0
    • 遍历数组A时,每个元素计数+1
  3. 匹配计算

    • 遍历数组B的每个元素
    • count_dict.get(num, 0) 获取该元素在A中的出现次数
    • 所有匹配次数累加到total
  4. 边界处理

    • 数组长度验证防止数据格式错误
    • 不存在的元素自动按0次处理

示例测试

示例1输入

5
4
1 2 3 4 5
4 3 2 1

输出

4

解析

  • A中每个元素出现1次
  • B中的4、3、2、1均能在A中找到
  • 总匹配次数 = 1+1+1+1 = 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次
  • 总匹配次数 = 2+2+0 = 4

综合分析

  1. 时间复杂度

    • 统计频率:O(M),遍历数组A一次
    • 匹配计算:O(N),遍历数组B一次
    • 总复杂度:O(M + N),线性时间复杂度
  2. 空间复杂度

    • 字典存储:最差O(M)(所有元素不同时)
    • 输入存储:O(M + N) 存储两个数组
  3. 性能优势

    • 相比暴力法的O(M*N),效率提升数百倍
    • 例如当M=N=105时,暴力法需1010次运算(不可行),而哈希法仅需2*10^5次
  4. 适用场景

    • 大规模数据处理(如M=1e6, N=1e6)
    • 需要频繁查询元素出现次数的场景
    • 元素取值范围较大的情况(哈希表不依赖连续空间)
  5. Python特性利用

    • 字典的get()方法简化了"存在性检查+默认值"逻辑
    • map()函数高效处理类型转换
    • 动态列表自动处理变长数据
  6. 扩展性

    • 支持非整数类型(只需可哈希)
    • 可轻松修改为统计三元组、四元组等
    • 适用于分布式计算(分块统计频率后合并)

JavaScript

问题分析

我们需要统计两个数组 A 和 B 中满足 A[i] == B[j] 的二元组 (i, j) 的总个数。直接遍历所有组合的时间复杂度为 O(M*N),但通过哈希表优化可以将时间复杂度降低到 O(M + N)。


解题思路

  1. 哈希表统计频率:遍历数组 A,用哈希表记录每个元素出现的次数。
  2. 遍历数组 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();
}

代码详细解析

  1. 输入处理

    const rl = readline.createInterface(...) // 创建输入接口
    rl.on('line', ...)                       // 监听每一行输入
    
    • 使用 Node.js 的 readline 模块逐行读取输入
    • 通过 switch 语句处理不同行的输入内容
  2. 数组验证

    if (A.length !== M) { ... } // 验证数组A长度
    if (B.length !== N) { ... } // 验证数组B长度
    
    • 检查输入数组长度是否与声明的长度一致
    • 发现不一致立即输出 0 并退出
  3. 哈希表统计

    const countMap = {};
    for (const num of A) {countMap[num] = (countMap[num] || 0) + 1;
    }
    
    • 使用普通对象作为哈希表
    • (countMap[num] || 0) 实现类似 Python 的 get() 方法
  4. 匹配计算

    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 中找到
  • 总匹配次数 = 1+1+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次
  • 总匹配次数 = 2+2+0 = 4

综合分析

  1. 时间复杂度

    • 统计频率:O(M),遍历数组A一次
    • 匹配计算:O(N),遍历数组B一次
    • 总复杂度:O(M + N),线性时间复杂度
  2. 空间复杂度

    • 哈希表存储:最差 O(M)(所有元素不同时)
    • 输入存储:O(M + N) 存储两个数组
  3. 性能优势

    • 相比暴力法 O(M*N) 的复杂度,效率提升数百倍
    • 例如当 M=N=10^5 时,暴力法需要 1e10 次运算(不可行),而哈希法仅需 2e5 次
  4. JavaScript 特性利用

    • 对象动态属性实现哈希表
    • || 运算符实现默认值
    • map(Number) 快速类型转换
  5. 扩展性

    • 支持非数字类型(需可哈希)
    • 可轻松修改为统计三元组等复杂场景
    • 适用于浏览器和 Node.js 双环境

C++

问题分析

给定两个数组A和B,统计满足A[i] == B[j]的二元组(i,j)的总个数。直接遍历所有组合的时间复杂度为O(M*N),但通过哈希表优化可以将时间复杂度降低到O(M + N)。


解题思路

  1. 哈希表统计频率:遍历数组A,用unordered_map记录每个元素出现的次数。
  2. 遍历数组B匹配:遍历数组B,对于每个元素,在哈希表中查找其出现次数并累加。

代码实现

#include <iostream>
#include <vector>
#include <sstream>
#include <unordered_map>using namespace std;int main() {int M, N;// 读取数组A和B的长度cin >> M >> N;// 清除输入缓冲区中的换行符cin.ignore(numeric_limits<streamsize>::max(), '\n');// 读取数组A的元素string lineA;getline(cin, lineA);vector<int> 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);vector<int> B;stringstream ssB(lineB);while (ssB >> num) {B.push_back(num);}// 验证数组B长度if (B.size() != N) {cout << 0 << endl;return 0;}// 统计数组A中每个元素的出现次数unordered_map<int, 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;
}

代码逐行解析

  1. 输入处理

    cin >> M >> N;  // 读取数组A和B的长度
    cin.ignore(...); // 清除缓冲区中的换行符
    getline(cin, lineA); // 读取数组A的元素行
    
    • 使用cin读取数组长度后,必须用cin.ignore()清除缓冲区残留的换行符
    • getline按行读取数组元素,避免空格和换行符干扰
  2. 数组元素解析

    stringstream ssA(lineA); // 将字符串转换为流
    while (ssA >> num) { ... } // 逐个读取整数
    
    • stringstream将字符串按空格分割为整数流
    • vector动态存储数组元素
  3. 哈希表统计

    unordered_map<int, int> countMap;
    for (int num : A) { countMap[num]++; }
    
    • unordered_map以O(1)时间复杂度实现键值查找
    • 遍历数组A时,每个元素在哈希表中计数+1
  4. 匹配次数计算

    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中找到,总匹配次数=1+1+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次,3匹配0次
  • 总匹配次数=2+2+0=4

综合分析

  1. 时间复杂度

    • 统计频率:O(M),遍历数组A一次
    • 匹配计算:O(N),遍历数组B一次
    • 总复杂度:O(M + N),线性时间复杂度
  2. 空间复杂度

    • 哈希表存储:最差O(M)(所有元素不同时)
    • 输入存储:O(M + N) 存储两个数组
  3. 性能优势

    • 相比暴力法的O(M*N),效率提升数百倍
    • 例如当M=N=10^5时,暴力法需要1e10次运算(不可行),哈希法仅需2e5次
  4. C++特性利用

    • unordered_map实现哈希表,平均O(1)查询时间
    • stringstream处理复杂的输入分割逻辑
    • vector动态数组自动管理内存
  5. 扩展性

    • 支持非整型数据(需自定义哈希函数)
    • 可轻松修改为统计三元组等复杂场景
    • 适用于高性能计算场景(如嵌入式系统)

C语言

问题分析

我们需要统计两个数组A和B中满足A[i] == B[j]的二元组(i,j)的总个数。直接遍历所有组合的时间复杂度为O(M*N),但通过哈希表优化可以将时间复杂度降低到O(M + N)。


解题思路

  1. 哈希表统计频率:遍历数组A,使用哈希表记录每个元素出现的次数。
  2. 遍历数组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;
}

代码详细解析

  1. 哈希表结构定义

    • HashNode:链表节点,存储键、值和下一个节点的指针。
    • HashMap:哈希表结构,包含桶数组和大小。
  2. 哈希表操作

    • createHashMap:分配内存,初始化桶数组。
    • put:插入元素。若键存在,计数加1;否则新建节点插入链表头部。
    • get:查询键的出现次数,遍历链表查找。
    • freeHashMap:释放哈希表所有节点内存。
  3. 输入处理

    • 使用fgets逐行读取输入,strtok分割字符串。
    • 验证数组长度是否与输入一致,避免数据错误。
  4. 核心逻辑

    • 遍历数组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。

综合分析

  1. 时间复杂度

    • 统计频率:O(M),遍历数组A一次。
    • 匹配计算:O(N),遍历数组B一次。
    • 总复杂度:O(M + N),线性时间复杂度。
  2. 空间复杂度

    • 哈希表:O(M),存储数组A元素的频次。
    • 输入数组:O(M + N),存储原始数据。
  3. 优势

    • 高效性:避免暴力法的O(M*N)复杂度。
    • 通用性:支持任意整数(包括负数),哈希函数处理简单。
  4. 适用场景

    • 大规模数据,如M和N达到10^5级别。
    • 需要快速统计元素频次并匹配的场景。

GO

问题分析

给定两个数组A和B,统计满足A[i] == B[j]的二元组(i,j)的总个数。直接遍历所有组合的时间复杂度为O(M*N),但通过哈希表优化可以将时间复杂度降低到O(M + N)。


解题思路

  1. 哈希表统计频率:遍历数组A,用map记录每个元素出现的次数。
  2. 遍历数组B匹配:遍历数组B,对于每个元素,在哈希表中查找其出现次数并累加。

代码实现

package mainimport ("bufio""fmt""os""strconv""strings"
)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)
}

代码详细解析

  1. 输入处理

    • bufio.Scanner:创建输入扫描器逐行读取数据。
    • strconv.Atoi:将字符串转换为整数,用于读取数组长度。
    • strings.Fields:按空格分割字符串,处理数组元素。
  2. 数组验证

    if len(A) != M { ... }  // 验证数组A长度
    if len(B) != N { ... }  // 验证数组B长度
    
    • 检查分割后的元素数量是否与声明的长度一致。
  3. 哈希表统计

    countMap := make(map[string]int)
    for _, numStr := range A {countMap[numStr]++
    }
    
    • 使用字符串直接作为键(避免类型转换开销)。
    • 遍历数组A时,每个字符串元素计数+1。
  4. 匹配计算

    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。

综合分析

  1. 时间复杂度

    • 统计频率:O(M),遍历数组A一次。
    • 匹配计算:O(N),遍历数组B一次。
    • 总复杂度:O(M + N),线性时间复杂度。
  2. 空间复杂度

    • 哈希表存储:O(M),存储数组A元素的字符串形式。
    • 输入存储:O(M + N),存储原始字符串数据。
  3. 性能优化

    • 直接使用字符串键:避免多次类型转换。
    • 哈希表快速查找:Go的map实现基于哈希表,平均O(1)查询时间。
  4. 适用场景

    • 适用于大规模数据(如M=1e6, N=1e6)。
    • 需要快速统计元素出现次数的场景。
    • 元素包含非数字字符的场景(如"apple")。
  5. 扩展性

    • 支持任意可哈希类型(如结构体)。
    • 可轻松修改为统计三元组、四元组等。

更多内容:

https://www.kdocs.cn/l/cvk0eoGYucWA

本文发表于【纪元A梦】,关注我,获取更多实用教程/资源!

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com