跳至主要內容

2025A-统计匹配的二元组个数

题目描述与示例

题目

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

题目练习网址：https://www.algomooc.com/problem/P2806

输入描述

第一行输入数组 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]，存在两种情况：

  1. 如果它在B中没有出现，那么能构成的二元组的个数为0
  2. 如果它在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

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频

# 导入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++

#include <iostream>
#include <unordered_map>
#include <vector>

int main() {
    int nA, nB;
    std::cin >> nA;
    std::cin >> nB;

    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;
}

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 1000  // 假设最大元素值为1000，可以根据实际需求调整

// 哈希表结构体
typedef struct {
    int value;
    int count;
} HashMap;

// 哈希表函数
int hash(int key) {
    return key % MAX;
}

// 插入哈希表
void insert(HashMap hashTable[], int key) {
    int idx = hash(key);
    while (hashTable[idx].count > 0 && hashTable[idx].value != key) {
        idx = (idx + 1) % MAX;
    }
    if (hashTable[idx].count == 0) {
        hashTable[idx].value = key;
    }
    hashTable[idx].count++;
}

// 查找哈希表
int find(HashMap hashTable[], int key) {
    int idx = hash(key);
    while (hashTable[idx].count > 0) {
        if (hashTable[idx].value == key) {
            return hashTable[idx].count;
        }
        idx = (idx + 1) % MAX;
    }
    return 0;
}

int main() {
    int nA, nB;
    scanf("%d", &nA);
    scanf("%d", &nB);

    HashMap cnt_A[MAX] = {0};  // 哈希表A
    HashMap cnt_B[MAX] = {0};  // 哈希表B

    // 读取集合A并插入哈希表
    for (int i = 0; i < nA; i++) {
        int num;
        scanf("%d", &num);
        insert(cnt_A, num);
    }

    // 读取集合B并插入哈希表
    for (int i = 0; i < nB; i++) {
        int num;
        scanf("%d", &num);
        insert(cnt_B, num);
    }

    // 计算匹配的二元组个数
    int result = 0;
    for (int i = 0; i < MAX; i++) {
        if (cnt_A[i].count > 0) {
            result += cnt_A[i].count * find(cnt_B, cnt_A[i].value);
        }
    }

    printf("%d\n", result);
    return 0;
}

Node JavaScript

// 使用一个对象作为哈希表
const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

// 输入读取
rl.question('', (nA) => {
    rl.question('', (nB) => {
        rl.question('', (a) => {
            rl.question('', (b) => {
                const cnt_A = {};
                const cnt_B = {};
                
                // 读取集合A并统计频次
                a.split(' ').forEach(num => {
                    cnt_A[num] = (cnt_A[num] || 0) + 1;
                });

                // 读取集合B并统计频次
                b.split(' ').forEach(num => {
                    cnt_B[num] = (cnt_B[num] || 0) + 1;
                });

                // 计算匹配的二元组个数
                let result = 0;
                for (let num in cnt_A) {
                    if (cnt_B[num]) {
                        result += cnt_A[num] * cnt_B[num];
                    }
                }

                console.log(result);
                rl.close();
            });
        });
    });
});

Go

package main

import (
        "fmt"
)

func main() {
        // 使用 fmt.Scanf 读取输入
        var nA, nB int
        fmt.Scan(&nA)
        fmt.Scan(&nB)

        // 使用 map 来存储集合A和集合B的元素频次
        cntA := make(map[int]int)
        cntB := make(map[int]int)

        // 读取集合A并统计频次
        for i := 0; i < nA; i++ {
                var num int
                fmt.Scan(&num)
                cntA[num]++ // 增加该数字在集合A中的出现次数
        }

        // 读取集合B并统计频次
        for i := 0; i < nB; i++ {
                var num int
                fmt.Scan(&num)
                cntB[num]++ // 增加该数字在集合B中的出现次数
        }

        // 计算匹配的二元组个数
        total := 0
        for num, countA := range cntA {
                if countB, exists := cntB[num]; exists {
                        // 如果集合B中也包含该数字
                        total += countA * countB // 计算匹配的二元组个数
                }
        }

        // 输出结果
        fmt.Println(total)
}

时空复杂度

时间复杂度：O(N+M)。需要遍历数组构建哈希表。

空间复杂度：O(N+M)。哈希表所占用空间。

本站内容包括机考真题解析、八股文速记、技术&行为面试指南、真实上岸经验与截图墙。
Copyright © 2025 欧弟算法