欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

开花(在b数组中二分查找a数组元素)

程序员文章站 2022-05-26 08:40:19
...

开花(在b数组中二分查找a数组元素)
开花(在b数组中二分查找a数组元素)

注意:
代码一:二层循环暴力查找超时
代码二(最棒):借用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;
}