首页 > 代码库 > 倒排文档

倒排文档



第一行输出该词所在的行数序号(多个的话,按照从小到大排序输出,中间空格隔开,序号从一开始记),如果没有出现,输出 -1
第二行输出频次排名R的单词出现的次数。
测试数据中的词频的分布如下,可见,排名第3的词,出现的次数为2
I,4
Beijing,2
in,2
love,2
.,1
Bejing,1
a,1
also,1
am,1
and,1
beautiful,1
is,1
life,1
live,1
student,1
there,1

travelling,1


这题很简单,参考答案是这样的:

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;

const int NN=100; //单词总数
const int MM=100000; //文本单行最大字符数

/* 文本单行 */
char ss[MM];
/* 统计频次 */
map<string,int> Mmap;
/* 用于最后的频次排序 */
struct node
{
    int x;
    string s;
}a[NN];

/* 用于最后的频次排序的排序规则 */
bool cmp(node xx,node yy)
{
    if(xx.x==yy.x)
        return xx.s<yy.s;
    return xx.x>yy.x;
}

bool fun(char *p,string temp)
{
    bool fg=false;  //此行中,是否有temp
    string t="";
    for(int i=0;*(p+i);i++)
    {
        if(*(p+i)==‘ ‘)
        {
            if(t.size()>0)
            {
                if(Mmap.count(t)==0)
                {
                    Mmap[t]=1;
                }
                else
                    Mmap[t]++;
                if(t==temp)
                    fg=true;
            }
            t="";
        }
        else
            t+=*(p+i);
    }

    if(t.size()>0)
    {
        if(Mmap.count(t)==0)
        {
            Mmap[t]=1;
        }
        else
            Mmap[t]++;
        if(t==temp)
            fg=true;
    }

    return fg;
}

int main()
{
    string temp;
    int n,R,tol=0;

    queue<int>ans; //存放查询单词出现的行数

    cin>>temp>>n>>R;
    getchar();

    for(int i=0;i<n;i++)
    {
        gets(ss);

       // cout<<"ss=="<<ss<<endl;

        if( fun(ss,temp) )
            ans.push(i+1);
    }

    map<string,int>::iterator itt = Mmap.begin();
    while(itt!=Mmap.end())
    {
        a[tol].s=(*itt).first;
        a[tol].x=(*itt).second;

      //  cout<<(*itt).first<<" "<<(*itt).second<<endl;

        tol++;
        itt++;
    }

    sort(a,a+tol,cmp);

    if(ans.size()>0)
    {
        int x=ans.front();
        ans.pop();
        printf("%d",x);
        while(!ans.empty())
        {
            x=ans.front();
            ans.pop();
            printf(" %d",x);
        }
        puts("");
    }
    else
        puts("-1");

    cout<<a[R-1].x<<endl;

    return 0;
}