阿里算法岗 0530笔试真题 - 多约束条件下的元素匹配统计
多约束条件下的元素匹配统计
阿里算法岗 0530笔试 第二题
题目内容
给定三个长度为n nn的数组{ a 1 , a 2 , … , a n } \{a_1, a_2, \dots, a_n\}{a1,a2,…,an}、{ b 1 , b 2 , … , b n } \{b_1, b_2, \dots, b_n\}{b1,b2,…,bn}和{ c 1 , c 2 , … , c n } \{c_1, c_2, \dots, c_n\}{c1,c2,…,cn}。这里c j c_jcj表示对数组b bb的一个下标。 请你统计满足以下条件的有序对( i , j ) (i, j)(i,j)的数量：
- 1 ≤ i ≤ j ≤ n 1 \le i \le j \le n1≤i≤j≤n；
- a i = b c j a_i = b_{c_j}ai=bcj。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数T TT（1 ≤ T ≤ 2 × 10 5 1 \le T \le 2 \times 10^51≤T≤2×105）代表数据组数；除此之外，保证单个测试文件的n nn之和不超过2 × 10 5 2 \times 10^52×105。 每组测试数据的输入格式如下：
- 第一行输入一个整数n nn（1 ≤ n ≤ 10 5 1 \le n \le 10^51≤n≤105）；
- 第二行输入n nn个整数a 1 , a 2 , … , a n a_1, a_2, \dots, a_na1,a2,…,an（1 ≤ a i ≤ 10 9 1 \le a_i \le 10^91≤ai≤109）；
- 第三行输入n nn个整数b 1 , b 2 , … , b n b_1, b_2, \dots, b_nb1,b2,…,bn（1 ≤ b i ≤ 10 9 1 \le b_i \le 10^91≤bi≤109）；
- 第四行输入n nn个整数c 1 , c 2 , … , c n c_1, c_2, \dots, c_nc1,c2,…,cn（1 ≤ c j ≤ n 1 \le c_j \le n1≤cj≤n）。
输出描述
对于每一组测试数据，新起一行输出一个整数，表示满足条件的有序对数量。
样例1
输入
2 5 1 2 1 2 1 2 1 3 1 2 2 1 5 4 3 3 7 7 7 1 2 7 3 3 3输出
5 6题解
思路
哈希表
- 从前往后枚举
j,当前可以组成的合法有序对是a下标为(1, j)中值等于b[c[j]]的数量。 - 按照1的分析，并且随着
j递增，不同数字的数量只会增加不会减少，所以可以定义numCount哈希表统计前[1,j]a各种数的数量。 - 从前往后枚举j，每次j递增时，更新
numCount[a[j]]++，并增加当前j情况下能组成的合法有序对ans += numCount[b[c[j]]]
C++
#include<bits/stdc++.h>usingnamespacestd;intmain(){ios_base::sync_with_stdio(false);cin.tie(nullptr);intT;cin>>T;while(T--){intn;cin>>n;vector<int>a(n+1),b(n+1),c(n+1);for(inti=1;i<=n;i++){cin>>a[i];}for(inti=1;i<=n;i++){cin>>b[i];}for(inti=1;i<=n;i++){cin>>c[i];}// 记录下标小于j中a每种数字的数量unordered_map<int,int>numCount;intans=0;for(intj=1;j<=n;j++){numCount[a[j]]++;ans+=numCount[b[c[j]]];}cout<<ans<<endl;}return0;}java
importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intT=sc.nextInt();while(T-->0){intn=sc.nextInt();int[]a=newint[n+1];int[]b=newint[n+1];int[]c=newint[n+1];for(inti=1;i<=n;i++){a[i]=sc.nextInt();}for(inti=1;i<=n;i++){b[i]=sc.nextInt();}for(inti=1;i<=n;i++){c[i]=sc.nextInt();}// 记录下标小于j中a每种数字的数量HashMap<Integer,Integer>numCount=newHashMap<>();longans=0;for(intj=1;j<=n;j++){numCount.put(a[j],numCount.getOrDefault(a[j],0)+1);ans+=numCount.getOrDefault(b[c[j]],0);}System.out.println(ans);}sc.close();}}python
fromcollectionsimportdefaultdict T=int(input())for_inrange(T):n=int(input())a=[0]+list(map(int,input().split()))b=[0]+list(map(int,input().split()))c=[0]+list(map(int,input().split()))# 记录下标小于j中a每种数字的数量num_count=defaultdict(int)ans=0forjinrange(1,n+1):num_count[a[j]]+=1ans+=num_count[b[c[j]]]print(ans)javascript
constreadline=require('readline');constrl=readline.createInterface({input:process.stdin,output:process.stdout});constlines=[];rl.on('line',(line)=>{lines.push(line);});rl.on('close',()=>{letidx=0;constT=Number(lines[idx++]);for(lett=0;t<T;t++){constn=Number(lines[idx++]);consta=[0,...lines[idx++].split(' ').map(Number)];constb=[0,...lines[idx++].split(' ').map(Number)];constc=[0,...lines[idx++].split(' ').map(Number)];// 记录下标小于j中a每种数字的数量constnumCount=newMap();letans=0;for(letj=1;j<=n;j++){numCount.set(a[j],(numCount.get(a[j])||0)+1);ans+=numCount.get(b[c[j]])||0;}console.log(ans);}});Go
packagemainimport"fmt"funcmain(){varTintfmt.Scan(&T)forT>0{T--varnintfmt.Scan(&n)a:=make([]int,n+1)b:=make([]int,n+1)c:=make([]int,n+1)fori:=1;i<=n;i++{fmt.Scan(&a[i])}fori:=1;i<=n;i++{fmt.Scan(&b[i])}fori:=1;i<=n;i++{fmt.Scan(&c[i])}// 记录下标小于j中a每种数字的数量numCount:=make(map[int]int)varansint64=0forj:=1;j<=n;j++{numCount[a[j]]++ans+=int64(numCount[b[c[j]]])}fmt.Println(ans)}}