题目描述与示例
题目
给定两个数组 A
和 B
,若数组 A
的某个元素 A[i]
与数组 B
中的某个元素 B[j]
满足 A[i]==B[j]
,则寻找到一个匹配的二元组(i,j)
,请统计再这两个数组 A
和 B
中,一共存在多少个这样的二元组。
输入描述
第一行输入数组 A
的长度 M
; 第一行输入数组 B
的长度 N
; 第三行输入数组 A
的值; 第四行输入数组 B
的值。 1 ≤ M, N ≤ 100000
A
,B
数组中数值的取值均小于 100000
输出描述
输出匹配的二元组个数
示例一
输入
5
4
1 2 3 4 5
4 3 2 1
输出
4
说明
若下标从 0
开始,则匹配的二元组分别为(0,3)
,(1,2)
,(2,1)
,(3,0)
,共计 4
对二元组。
示例二
输入
6
3
1 2 4 4 2 1
1 2 3
输出
4
解题思路
数组 A
和 B
中各个元素的频率我们都需要统计,可以用两个哈希表进行储存,分别记为cnt_A
和cnt_B
。接下来我们就来统计能构成的二元组的个数。
接下来我们考虑如何计算二元组的数目。某一个数字num
在A
中出现的次数为cnt_A[num]
,存在两种情况:
- 如果它在
B
中没有出现,那么能构成的二元组的个数为0
- 如果它在
B
中出现过,出现次数为cnt_B[num]
,那么基于简单的乘法原理,能构成的二元组个数为cnt_A[num] * cnt_B[num]
以示例二为例子:元素1
在数组A
中出现了两次,下标分别为0
和5
,在数组B中出现了一次,下标为0
,所以对于元素1
可以构成2 * 1 = 2
组二元组,分别为(0, 0)
和(5, 0)
。元素2
也可以构成2
组二元组,分别为(1, 1)
和(4, 1)
。所以一共可以构成2 + 2 = 4
组二元组。
如果我们是使用计数器Counter()
来储存元素频率,上述两种情况其实可以合并。因为如果num
不位于cnt_B
的键中,我们会得到cnt_B[num] = 0
。因此计算cnt_A[num] * cnt_B[num] = 0
。
所以我们只需要遍历cnt_A
中的所有键num
,计算cnt_A[num]*cnt_B[num]
的结果并求和即可。
代码
Python
# 题目:2023Q1A-统计匹配的二元组个数
# 分值:200
# 作者:闭着眼睛学数理化
# 算法:哈希表
# 代码看不懂的地方,请直接在群上提问
# 导入collections中的Counter计数器类,使用dict()也可以,但是代码就要多一些判断
from collections import Counter
nA = int(input())
nB = int(input())
cnt_A = Counter(input().split())
cnt_B = Counter(input().split())
# 基于乘法原理,计算能够构成的二元组的个数
print(sum(cnt_A[num] * cnt_B[num] for num in cnt_A))
Java
import java.util.HashMap;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int nA = scanner.nextInt();
int nB = scanner.nextInt();
HashMap<Integer, Integer> cnt_A = new HashMap<>();
HashMap<Integer, Integer> cnt_B = new HashMap<>();
for (int i = 0; i < nA; i++) {
int num = scanner.nextInt();
cnt_A.put(num, cnt_A.getOrDefault(num, 0) + 1);
}
for (int i = 0; i < nB; i++) {
int num = scanner.nextInt();
cnt_B.put(num, cnt_B.getOrDefault(num, 0) + 1);
}
long total = 0;
for (int num : cnt_A.keySet()) {
if (cnt_B.containsKey(num)) {
int countA = cnt_A.get(num);
int countB = cnt_B.get(num);
total += (long) countA * countB;
}
}
System.out.println(total);
}
}
C++
“`C++
#include <iostream>
#include <unordered_map>
#include <vector>
int main() {
int nA, nB;
std::cin >> nA;
std::cin >> nB;
<pre><code>std::unordered_map<int, int> cnt_A;
std::unordered_map<int, int> cnt_B;
for (int i = 0; i < nA; ++i) {
int num;
std::cin >> num;
cnt_A[num]++;
}
for (int i = 0; i < nB; ++i) {
int num;
std::cin >> num;
cnt_B[num]++;
}
long long total = 0;
for (const auto& pair : cnt_A) {
int num = pair.first;
int countA = pair.second;
int countB = cnt_B[num];
total += static_cast<long long>(countA) * countB;
}
std::cout << total << std::endl;
return 0;
</code></pre>
}
“`
时空复杂度
时间复杂度:O(N+M)
。需要遍历数组构建哈希表。
空间复杂度:O(N+M)
。哈希表所占用空间。
说明
华为OD机试有三道题⽬,第⼀道和第⼆道属于简单或中等题,分值为 100 分,第三道为中等或困难题,分值为 200分,总分为 400 分。
机试分数越⾼评级越⾼,⼯资也就越⾼。
关于华为 OD 机试更加详细的介绍可以查看这篇⽂章:华为OD机考须知
关于机考题目汇总可以看这篇文章:华为OD机试真题 2023 A+B+C+D卷 + 2024新卷(Python&Java&C++)⽬录汇总(每⽇更新)