单词分组(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行...且十分丑,就不贴了...
评论