A106103题解

在锣鼓的题解被飞升了，详见此

---

题目大意

给出 $n$ 个和 $m$ 个数，求出这 $m$ 个数里能找到多少个数也在这 $n$ 个数里。

思路

看到这数据量的时候（$1≤n,m≤10^5$），就知道遍历两个数组肯定是会 TLE 的，第一时间想到了可以用二分来找，这样只要先排个序，再二分一下 $B$ 数组就可以了，时间复杂度简化到了 $O((n+m)\log m)$。

AC Code：

namespace HQ{
    void init(){
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }int n,m,a[110000],b[110000];
    bool isfind(int x){
        int l=1,r=m;
        while(l<=r){
            int mid=(l+r)/2;
            if(b[mid]==x)return 1;
            else if(b[mid]>x)r=mid-1;
            else l=mid+1;
        }return 0;
    }bool cmp(int x,int y){
        return x<y;
    }void Main(){
        init();
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }for(int i=1;i<=m;i++){
            cin>>b[i];
        }sort(b+1,b+m+1,cmp);
        int cnt=0;
        for(int i=1;i<=n;i++){
            if(isfind(a[i]))cnt++;
        }cout<<cnt;
        return;
    }
}