【华为OD-E卷-统计匹配的二元组个数 100分（python、java、c++、js、c）】

题目

给定两个数组A和B，若数组A的某个元素A[i]与数组B中某个元素B[j]满足 A[i] == B[j]，则寻找到一个值匹配的二元组(i,j)。 请统计在这两个数组A和B中，一共存在多少个这样的二元组。

输入描述

• 第一行输入数组A的长度M，

第二行输入数组B的长度N，

第三行输入数组A的值，

第四行输入数组B的值

输出描述

• 输出匹配的二元组个数

备注

• 若不存在相等的值，则输出0。 所采用的算法复杂度需小于O(N^2),否则会超时。 输入数组中允许出现重复数字，一个数字可以匹配多次

用例

用例一：

输入：

5
4
1 2 3 4 5
4 3 2 1

• 1
• 2
• 3
• 4

输出：

4

• 1

用例二：

输入：

6
3
1 2 4 4 2 1
1 2 3

• 1
• 2
• 3
• 4

输出：

4

• 1

python解法

• 解题思路：
• 首先输入两个整数 m 和 n，表示两个数组 a 和 b 的大小。
  接着输入两个列表 a 和 b，分别包含 m 个元素和 n 个元素。
  任务是统计数组 b 中有多少个元素在数组 a 中出现过。这里的元素是可能重复的。
  可以通过字典 counts 来存储数组 a 中每个元素出现的次数。然后遍历数组 b，每遇到一个在 a 中存在的元素，就将其计入匹配次数。
  最后输出匹配的总次数。

def solve():
    # 读入m和n
    m = int(input())  # 数组a的大小
    n = int(input())  # 数组b的大小

    # 读入数组a和b
    a = input().split()  # 数组a的元素
    b = input().split()  # 数组b的元素

    # 初始化一个字典，用于记录数组a中每个元素的出现次数
    counts = {}
    matches = 0  # 记录b中与a匹配的元素个数

    # 遍历数组a，统计每个元素出现的次数
    for x in a:
        counts[x] = counts.get(x, 0) + 1

    # 遍历数组b，查看其中的元素在a中出现过多少次
    for y in b:
        matches += counts.get(y, 0)  # 如果y在a中存在，就增加匹配次数

    # 输出最终的匹配次数
    print(matches)

solve()

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26

java解法

• 解题思路
• 输入数据：首先输入两个整数 a 和 b，分别表示数组 arrA 和 arrB 的大小。接着输入两个字符串，分别是数组 arrA 和 arrB 的元素，元素之间用空格隔开。
  任务目标：统计数组 arrB 中的元素在数组 arrA 中出现的总次数。即数组 arrB 中每个元素在 arrA 中匹配到的次数总和。
  思路分析：
  使用一个 频率表（Map） 来记录数组 arrA 中每个元素出现的次数。
  遍历数组 arrB，查找数组 arrA 中每个元素出现的次数，并累加到结果中。
  代码步骤：
  通过 countFreq 方法统计数组 arrA 中每个元素的出现频率，返回一个 Map。
  通过 calcMatches 方法遍历数组 arrB，并使用频率表查找每个元素在 arrA 中的出现次数，最终返回匹配次数。
  时间复杂度：假设数组 arrA 和 arrB 的长度分别为 a 和 b，那么时间复杂度是 O(a + b)，因为分别遍历了两次数组。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 创建Scanner对象，读取输入
        Scanner sc = new Scanner(System.in);

        // 读入数组arrA和arrB的大小，虽然a和b并不直接使用
        int a = Integer.parseInt(sc.nextLine()); // 数组arrA的大小
        int b = Integer.parseInt(sc.nextLine()); // 数组arrB的大小

        // 读入数组arrA和arrB的元素，使用空格分割
        String[] arrA = sc.nextLine().split(" "); // 数组arrA的元素
        String[] arrB = sc.nextLine().split(" "); // 数组arrB的元素

        // 统计数组arrA中每个元素的出现频率
        Map<String, Integer> freqMap = countFreq(arrA);

        // 计算数组arrB中元素在arrA中的匹配总次数
        int result = calcMatches(freqMap, arrB);

        // 输出匹配次数
        System.out.println(result);
    }

    // 统计数组中每个元素出现的频率
    private static Map<String, Integer> countFreq(String[] arr) {
        // 创建一个HashMap，用于存储元素及其出现的频率
        Map<String, Integer> freqMap = new HashMap<>();
        
        // 遍历数组，更新频率表
        for (String s : arr) {
            // getOrDefault方法，如果s在freqMap中存在，返回其对应的值，否则返回0
            freqMap.put(s, freqMap.getOrDefault(s, 0) + 1);
        }
        return freqMap; // 返回频率表
    }

    // 根据频率表计算在另一个数组中的匹配数量
    private static int calcMatches(Map<String, Integer> freqMap, String[] arr) {
        int total = 0; // 用于存储匹配的总次数
        
        // 遍历数组arr，累加匹配次数
        for (String s : arr) {
            // 如果s在freqMap中有记录，则返回其频率，否则返回0
            total += freqMap.getOrDefault(s, 0);
        }
        
        return total; // 返回总匹配次数
    }
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52

C++解法

• 解题思路

更新中

• 1

C解法

• 解题思路

更新中

• 1

JS解法

• 解题思路

更新中

• 1

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏