开花(在b数组中二分查找a数组元素)
程序员文章站
2022-05-26 08:40:19
...
注意:
代码一:二层循环暴力查找超时
代码二(最棒):借用STL set中的count()方法快速搞定,且没有超时
so,集合查询应该很快
注意:count()时间复杂度是线性变换的
最坏的情况为O(n)
so,总体复杂度介于二层循环的O(n平方)和
代码三的O(n + log n)之间,还是可以的
代码三:规规矩矩用二分查找
二分查找每次减半,so时间复杂度为O(log n)
在查找算法中算比较好的,但是要先sort()
代码一:暴力
#include <bits/stdc++.h>
using namespace std;
int a[100005],b[100005],c[100005];
int main(){
int n,m,x;
set<int> s;
scanf("%d%d",&n,&m);
//cin >> n >> m;
for(int i = 1; i <= n; i++){
scanf("%d",&a[i]);
//cin >> a[i];
}
for(int i = 1; i <= m; i++){
scanf("%d",&c[i]);
// cin >> c[i];
}
int p =1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(a[i] == c[j]){
b[p++] = a[i];
}
}
}
for(int i = 1; i <= p-2; i++){
printf("%d ",b[i]);
//cout << b[i] << " ";
}
printf("%d\n",b[p-1]);
// cout << b[p-1] << endl;
return 0;
}
代码二:借助set
#include <bits/stdc++.h>
using namespace std;
int a[10005],b[100005];
int main(){
int n,m,x;
set<int> s;
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
for(int i = 1; i <= m; i++){
cin >> x;
s.insert(x);
}
int p =1;
for(int i = 1; i <= n; i++){
if(s.count(a[i]) == 1){
b[p++] = a[i];
}
}
for(int i = 1; i <= p-2; i++){
cout << b[i] << " ";
}
cout << b[p-1] << endl;
return 0;
}
二分查找
#include <bits/stdc++.h>
using namespace std;
int a[100005],b[100005],c[100005];
int halfsearch(int key,int l,int r){
while(l <= r){
int mid = (l+r)/2;
if(b[mid] == key){
return 1;
}else if(b[mid] < key){
l = mid + 1;
}else {
r = mid - 1;
}
}
return 0;
}
int main(){
int n,m;
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+1+m);
int p = 1;
for(int i = 1; i <= n; i++){
if (halfsearch(a[i],1,m) == 1){ //在b中找a[i]
c[p++] = a[i];
}
}
for(int i = 1; i <= p-2; i++){
cout << c[i] << " ";
}
cout << c[p-1] << endl;
return 0;
}