1049. (算法作业3-1)数组中的频度

sort以后用upper_bound()减lower_bound()

这题虽然说要用分治，但是线性地做就行了吧……

#include "bits/stdc++.h"

using u64 = uint64_t;
int main() {
    u64 n, m;
    std::cin >> n >> m;
    std::unordered_map<u64, u64> freq;
    for (u64 i = 0; i < n; ++i) {
        u64 num; std::cin >> num;
        ++freq[num];
    }
    for (u64 i = 0; i < m; ++i) {
        u64 query; std::cin >> query;
        std::cout << freq[query] << '\n';
    }
}

一个新解法
[em:06]

Python用常规思路解这道题是行不通的，不过Python的标准库中的collections模块有个Counter类，使用Python的可以试一试

其实用map就可以很好解决了
map
key 是数组元素，value是对应元素出现的次数

include

include

include

include

using namespace std;

typedef long long LL;

LL a[100005];

int ans=0;

int find(LL a[], int s, int e, LL x){
if(s<=e){
int mid=(s+e)/2;
if(a[mid]x)find(a,s,mid-1,x);
if(a[mid]==x){
ans++;
find(a,s,mid-1,x);
find(a,mid+1,e,x);
}
}
return ans;
}

int main(){
int n,m;
LL x;
while(scanf(“%d%d”,&n,&m)==2){
memset(a,0,sizeof(a));
for(int i=1; i<=n; i++){
scanf(“%lld”,&a[i]);
}
sort(a+1,a+n+1);
for(int i=0; i<m; i++){
scanf(“%lld”,&x);
int s=1,e=n;
ans=find(a,s,e,x);
printf(“%d\n”,ans);
ans=0;
}
}
}