重名剔除(Deduplicate)

描述

Epicure先生正在编撰一本美食百科全书。为此,他已从众多的同好者那里搜集到了一份冗长的美食提名清单。既然源自多人之手,其中自然不乏重复的提名,故必须予以筛除。Epicure先生因此登门求助,并认定此事对你而言不过是“一碟小菜”,相信你不会错过在美食界扬名立万的这一良机

 

 

输入

第1行为1个整数n,表示提名清单的长度。以下n行各为一项提名

 

 

输出

所有出现重复的提名(多次重复的仅输出一次),且以其在原清单中首次出现重复(即第二次出现)的位置为序

 

 

输入样例

10

brioche

camembert

cappelletti

savarin

cheddar

cappelletti

tortellni

croissant

brioche

mapotoufu

 

 

输出样例

cappelletti

brioche

 

 

限制

1 < n < 6 * 10^5

提名均由小写字母组成,不含其它字符,且每项长度不超过40

时间:2 sec

空间:256MB

 

 

 

 

   我的想法是计算每个单词的各字母之和(a=1以此类推~~),然后以和的值为散列函数,采取开散列法,即拉链法存储各和值相同的单词,存到拉链的最后,这样在存储时就可以把拉链遍历一遍,这样就知道了是否有重复;并且在结构体里加一个couted来标示是否已经输出过,以此来保证每个重复元素只输出一遍~~

 

#include
//#include
//#include

using namespace std;

struct Hash
{
   Hash()
   {
       x[0]=’’;
       next=NULL;
       couted=false;
   }
   char x[80];
   Hash *next;
   bool couted;
}hash[10000];

void strcopy(char traget[],char source[])
{
   int i=0;//cout<<"source="<   do
   {
       traget[i]=source[i];//cout<<"source[i]="<    }while(source[i++]!=’’);
   //cout<<"traget="<        count=countstr(temp);//cout<        if(hash[count].x[0]==’’) strcopy(hash[count].x,temp);
       else
       {
           Hash *link,*pre;
           link=hash[count].next;
           pre=&hash[count];
           bool equal;
           equal=strequal(pre->x,temp);
           while(link!=NULL && !equal)
           {
               link=link->next;pre=pre->next;
               equal=strequal(pre->x,temp);
           }
           if(equal)
           {
               if(!pre->couted)
               {
                   cout<x<couted=true;
               }
           }
           else
           {
               Hash newhash;pre->next=&newhash;strcopy(newhash.x,temp);
           }

       }
       /*
       Hash *link;
       link=&hash[count];
       while(link!=NULL)
       {
           cout<x<<" ha ";link=link->next;
       }*/

 

   }

   return 0;
}

 

 

   但是提交到OJ上它说我超时~~这还有什么地方可以剪枝的吗?望大神能提示何处可以优化~~

重名剔除(Deduplicate)》上有2条评论

  1. Pingback引用通告: BZ编程小组 作品 | BZ编程小组

发表评论

电子邮件地址不会被公开。 必填项已用*标注