#include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; int a[n]; for(int i=0;i<n;i++) cin>>a[i]; int m; cin>>m; int b; for(int i=0;i<m;i++) { cin>>b; int d=0; for(int j=0;j<n;j++) { if(b==a[j]) d++; } if(i<m-1) cout<<d<<" "; else cout<<d<<endl; } return 0; }时间优化
时间: 2024-01-13 19:02:25 浏览: 42
这段代码的时间复杂度为O(m*n),可以通过使用哈希表来优化时间复杂度。具体做法为先将数组a中的元素插入到哈希表中,然后对于每个b,从哈希表中查找是否存在对应的元素,如果存在则计数器加1,最后输出计数器即可。这样时间复杂度就可以优化为O(m+n)。以下是优化后的代码:
```
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
unordered_map<int, int> mp;
for(int i=0;i<n;i++) {
int x;
cin>>x;
mp[x]++;
}
int m;
cin>>m;
for(int i=0;i<m;i++) {
int x;
cin>>x;
cout<<mp[x]<<" ";
}
cout<<endl;
return 0;
}
```
相关问题
#include <bits/stdc++.h> using namespace std;
这个头文件是C++11标准引入的,它包含了所有标准库中的头文件。使用这个头文件可以方便地在一个地方包含所有需要的头文件,而不需要一个一个地包含。这个头文件通常只在竞赛中使用,因为它不是标准C++头文件,不保证在所有编译器中都能正常工作。
以下是一个使用这个头文件的示例,实现输入4个整数a、b、c、d,将它们倒序输出:
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b, c, d;
cin >> a >> b >> c >> d;
cout << d << ' ' << c << ' ' << b << ' ' << a << endl;
return 0;
}
```
`#include+<bits/stdc++.h>
`#include <bits/stdc++.h>`是一个非标准的头文件,它包含了STL中所有的头文件,因此可以方便地使用STL中的各种数据结构和算法。但是需要注意的是,这个头文件并不是所有编译器都支持,比如在一些嵌入式系统中就不支持。如果你想在使用这个头文件的时候避免出现问题,可以使用以下两种方法:
1.手动添加需要的头文件,比如如果你只需要使用vector和algorithm,可以这样写:
```cpp
#include <vector>
#include <algorithm>
```
2.使用预编译头文件,将需要的头文件都包含在一个文件中,然后在需要使用的文件中包含这个预编译头文件。这样可以加快编译速度,但是需要注意的是,预编译头文件可能会占用较多的内存。
下面是一个使用`#include <bits/stdc++.h>`的示例,实现:依次输入4个整数a、b、c、d,将它们倒序输出,即依次输出d、c、b、a这4个数。
```cpp
#include <bits/stdc++.h>
using namespace std;
int a, b, c, d;
int main() {
cin >> a >> b >> c >> d;
cout << d << ' ' << c << ' ' << b << ' ' << a << endl;
return 0;
}
```