注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【模拟】【单词分组】  

2013-10-21 22:19:51|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
 

单词分组(Anagram)

 

一个单词是一个仅由小写字母构成的字符串,我们说两个单词属于同一组当且仅当组成他们的字母完全一样,比如abc和bac就是同组的,但是abcc和aabc不同组。现在给出一堆单词请你将他们分组输出。

 

输入格式:

       每行一个单词,直到文件末尾。单词个数小于50000。单词长度不超过30。

 

输出格式:

       输出5个最大的组,如果组数小于5个那么全部输出。输出按组的大小从大到小输出。如果有相同的按照组中字典序最小的元素排序,每组的所有单词也按照字典序排序输出,注意相同的单词仅输出一次。

 

样例输入:

 

undisplayed
trace
tea
singleton
eta
eat
displayed
crate
cater
carte
caret
beta
beat
bate
ate
abet

 

 

样例输出:

 

Group of size 5: caret carte cater crate trace .
Group of size 4: abet bate beat beta .
Group of size 4: ate eat eta tea .
Group of size 1: displayed .
Group of size 1: singleton .
==================================================================================
这一题关键在于两个部分,一个就是排序,一个是分组。
分组咱的想法就是使用HASH,由于有50000个字符串,所以取了3个模。(突然想起来这样子什么用都没有...)
HASH函数为 P=SIGMA(S[I]^I)MOD MODD;
然后对这个HASH值排序,就可以把相同的排在一起了。
然后扫一遍数组,记下HASH值相同的区间,并求出每个区间的LENGTH,然后再对LENGTH排序,length排好序之后就是答案了,但是又要求按字典序输出,所以我们还得对前五个区间中的字符串再排个序,然后取每个区间的最小的字符串,以长度为第一关键字,字符串大小为第二关键字再最后排次序...就可以了.....
HASH函数还写了一个快速幂,复杂度为O(NQLOGN)
然后对HASH值快排,复杂度为O(NQLOGN)
扫描数组复杂度为 O(N)
然后前五个区间的字符串排序,复杂度为O(5LOG30)即等于O(1)。
然后对每个区间的最小字符以LENGTH,SS为关键字排序,同为O(1)
总的复杂度为O(NQLOGN)。
然后费了180行...且十分丑,就不贴了...
  评论这张
 
阅读(21)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018