d478 - 共同的數 - 簡易版
題目描述
題目要求計算兩個已排序的正整數陣列的共同元素數量。輸入包含多組測試案例，每組案例包含兩個陣列，分別代表小潘和小花擁有的數字。
解題思路
對於每組測試案例，首先將兩個陣列合併，並移除不屬於兩個陣列的元素。然後，對合併後的陣列進行排序。最後，使用雙指標方法計算排序後陣列中相鄰元素相等的次數，即為共同元素的數量。
複雜度分析
- 時間複雜度: O(n * m * log(m))，其中 n 是測試案例的數量，m 是陣列的大小。主要時間花在排序上。
- 空間複雜度: O(m)，主要用於儲存合併後的陣列。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int a,b,ans,i,k,mina,minb,maxa,maxb,ba,bas;
cin >> a >> b;
b*=2;
ba=b;
for(;a>0;a--){
b=ba;
int c[b];
for(i=0;i<b;i++)
cin >> c[i];
mina=c[0];
minb=c[b/2];
maxa=c[b/2-1];
maxb=c[b-1];
for(i=0,bas=0;i<b;i++){
if((c[i]<mina||c[i]<minb)||(c[i]>maxa||c[i]>maxb)){
bas++;
c[i]=-1;
}
}
b-=bas;
int d[b];
for(i=0,k=0;i<ba;i++){
if(c[i]!=-1){
d[k]=c[i];
k++;
}
}
sort(d,d+b);
for(i=0,ans=0;i<b-1;i++){
if(d[i]==d[i+1]){
ans++;
i++;
}
}
cout << ans << endl;
}
}