当前位置：首页 > article >正文

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

article 2025/1/4 14:49:37

【华为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),否则会超时。输入数组中允许出现重复数字，一个数字可以匹配多次

用例

用例一：

输入：

输出：

用例二：

输入：

6
3
1 2 4 4 2 1
1 2 3

输出：

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

java解法

解题思路
输入数据：首先输入两个整数 a 和 b，分别表示数组 arrA 和 arrB 的大小。接着输入两个字符串，分别是数组 arrA 和 arrB 的元素，元素之间用空格隔开。
任务目标：统计数组 arrB 中的元素在数组 arrA 中出现的总次数。即数组 arrB 中每个元素在 arrA 中匹配到的次数总和。
思路分析：
使用一个频率表（Map）来记录数组 arrA 中每个元素出现的次数。
遍历数组 arrB，查找数组 arrA 中每个元素出现的次数，并累加到结果中。
代码步骤：
通过 countFreq 方法统计数组 arrA 中每个元素的出现频率，返回一个 Map<String, Integer>。
通过 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; // 返回总匹配次数
    }
}