刷题笔记合集🔗

二元组个数

问题描述

小柯有两个数组 和 ，若 则称 为一个二元组，求在给定的两个数组中，二元组的个数。

输入格式

第一行输入 。 第二行输入 个数，表示第一个数组。

第三行输入 。 第四行输入 个数，表示第二个数组。

输出格式

二元组个数。

样例输入

4
1 2 3 4
1
1

6
1 1 2 2 4 5
3
2 2 4

样例输出

1

5

数据范围

• 数组长度不超过
• 数组元素为整数

样例	解释说明
样例1	二元组个数为1个。, ，组成一个二元组。
样例2	二元组个数为5个。 中有两个1， 中有零个1； 中有两个2， 中有两个2； 中有一个4， 中有一个4； 中有一个5， 中有零个5。所以二元组个数为 个。

题解

这道题目要求计算两个数组中能形成的二元组个数，其中二元组定义为数组 和数组 中相同值的元素对 。

思路分析

最直接的解法是使用双重循环，遍历数组 和数组 的每一个元素，统计满足 的对数。

但是当数据规模较大时，双重循环的时间复杂度为 ，可能导致超时。因此，我们可以采用更高效的哈希表方法。

优化的方法是：

1. 统计两个数组中共同存在的元素
2. 分别计算这些元素在两个数组中的出现次数
3. 对于每个共同元素，其形成的二元组数量为该元素在数组 中的出现次数乘以在数组 中的出现次数

具体步骤

1. 将数组 和数组 的元素分别放入集合 和 中，用于快速查找共同元素
2. 遍历数组 ，统计每个在 中出现的元素的次数到 中
3. 遍历数组 ，统计每个在 中出现的元素的次数到 中
4. 遍历 中的每个元素，将其出现次数与 中对应元素的出现次数相乘，累加得到最终结果

时间复杂度分析

• 构建集合和统计元素频次的时间复杂度为
• 最终计算二元组个数的时间复杂度为 ，其中 是共同元素的个数，一般远小于 和

这种方法的总时间复杂度为 ，相比于双重循环的 ，大大提高了效率，适合处理题目给出的数据规模。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取输入
m = int(input())
a_arr = list(map(int, input().split()))

n = int(input())
b_arr = list(map(int, input().split()))

def count_pairs():
    """计算二元组个数"""
    # 创建两个数组的元素集合
    a_set = set(a_arr)
    b_set = set(b_arr)
    
    # 统计a数组中元素出现次数
    a_count = {}
    for val in a_arr:
        # 只统计b_set中存在的元素
        if val in b_set:
            a_count[val] = a_count.get(val, 0) + 1
    
    # 统计b数组中元素出现次数
    b_count = {}
    for val in b_arr:
        # 只统计a_set中存在的元素
        if val in a_set:
            b_count[val] = b_count.get(val, 0) + 1
    
    # 计算二元组总数
    total = 0
    for val in a_count:
        # 每个共同值的二元组数量 = a中出现次数 × b中出现次数
        total += a_count[val] * b_count[val]
    
    return total

# 输出结果
print(count_pairs())

• Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 读取输入
    int m;
    cin >> m;
    vector<int> a(m);
    for (int i = 0; i < m; i+