查找（二分、hash、桶）

先上一个最简单的题

1230 元素查找

给出n个正整数，然后有m个询问，每个询问一个整数，询问该整数是否在n个正整数中出现过。

输入描述 Input Description

第一行两个整数 n 和m。

第二行n个正整数（1<=n<= 100000）

第三行m个整数(1<=m<=100000)

输出描述 Output Description

一共m行，若出现则输出YES，否则输出NO

这个题数据很小，既可以用二分、桶、做，也可以用hash来做

用桶的思想来做的话是最简单的，定义一个bool数组，出现的正整数在数组里标记为TRUE；查找sum有没有出现过时只需要调用bool下标为sum的数组就行。

#include<iostream>

using namespace std;

bool s[];

int m,n;

int main()

{

    cin>>n>>m;

    for(int i=;i<=n;++i)

    {

        int sum;

        cin>>sum;

        s[sum]=true;

    }

    for(int i=;i<=m;++i)

    {

        int sum;

        cin>>sum;

        if(s[sum])cout<<"YES\n";

        else cout<<"NO\n";

    }

    return ;

}

桶

如果数据进一步升级，出现过的数进一步增大，空间进一步限制，这时用bool就不行了，需要用到二分查找，先存数，然后查找即可；

#include<iostream>

#include<algorithm>

#include<string>

using namespace std;

bool boo[];

int s[];

int n,m;

bool  find(int sum)

{

    int right=n,left=;

    while(right>=left)

    {

        int mid=left+(right-left)/;

        if(s[mid]==sum)return true;

        if(mid<sum)left=mid+;

        else right=mid-;

    }

    return ;

}

int main()

{

    cin>>n>>m;

    for(int i=;i<=n;++i)

        cin>>s[i];

    sort(s+,s+n+);

    for(int i=;i<=m;++i)

    {

        int sum;

        cin>>sum;

        if(find(sum))

            cout<<"YES"<<endl;

        else cout<<"NO"<<endl;

    }

    return ;

}

二分查找

最后，如果再进一步升级，咳咳，还是用hash吧；

这里是把数模一个数，然后建立以余数和数的边，查找是将待查找的数取余，查找余数所连接的边。

#include<iostream>

#define mod 4567;

using namespace std;

struct node

{

    int a,b,next;

};

node s[];

int head[],sum=;

int m,n;

void push(int a,int b)

{

    s[sum].a=a;

    s[sum].b=b;

    s[sum].next=head[a];

    head[a]=sum++;

}

bool find (long long sum)

{

    int x=sum%mod;

    int y=sum/mod;

    for(int k=head[x];k!=-;k=s[k].next)

        if(s[k].b==y)return true;

}

int main()

{

    for(int i=;i<=;++i)

        head[i]=-;

    int m,n;

    cin>>m>>n;

    for(int i=;i<=m;++i)

    {

        long long sum;

        cin>>sum;

        int x=sum%mod;

        int y=sum/mod;

        push(x,y);

    }

    for(int i=;i<=n;++i)

    {

        long long sum;

        cin>>sum;

        if(find(sum))

            cout<<"YES\n";

        else cout<<"NO\n";

    }

    return ;

}

hash

当然，选用其他的hash函数也是可以的，例如将数的每一位数字加起来，建立边表；当然，选择hash函数的原则对于每一个映射有尽量少的值与之对应，也就是一一对应关系

例如：hash函数%10;则对于1和11，他们对应的hash值一样，就需要存储下每个值，那么算法就会变慢，n为映射值相同的数的数目。

当然，hash所映射的不光是整数，字符串也可以；

现在我又找到了另外一种方法，用STL里的容器MAP就可以；

map是一种关联容器，恩。

看了下百科，表示没看懂；

#include<iostream>

#include<map>

using namespace std;

map<string,int>mapp;

int main()

{

    int n,m;

    cin>>n>>m;

    for(int i=;i<=n;++i)

    {

        string s;

        cin>>s;

        mapp.insert(map<string,int>::value_type(s,i));

    }

    while(m--)

    {

        string number;

        cin>>number;

        if(mapp.count(number))

            cout<<"YES"<<endl;

        else cout<<"NO"<<endl;

    //    if(mapp.find(number)!=mapp.end())

    //        cout<<"YES"<<endl;

    //    else cout<<"NO"<<endl;

    }

    return ;

}

代码

巴特西

查找（二分、hash、桶）

最新文章

热门文章