Nickname

Description

ZSUQ Messenger is similar with Tencent QQ. Each user will make a nickname for itself. Different users can have identical nickname. Some common ones, such as “Tom”, “Marry”, “Kate”, are frequently used. In a recent survey, the ZSUQ Company was astonished to find that there are no more than 5000 distinct nicknames that are being used.
       Being a member of the ZSUQ Company, you are asked to make a report, telling the number of users for each nick name. A complete list of all users’ nicknames is provided to you. Please note that nicknames are case insensitive.
Input
The first line of the file contains an integer indicating the number of test cases.
In each test case, there is an integer N in the first line (0 < N < 100,000). The following N lines describe N users’ nicknames. Each name consists of no more than 100 characters. There is a bland line between two cases.
Output
For each case, give out a list of the distinct nickname, one per line, followed by a bland space and the number of users who has this nickname. The names are in alphabetic order. There is no bland space at the beginning or the end of each line. Nicknames should be presented in lowercase letter. There is a bland line after each case.

 

题目：一组个数为N（<=100,000）的昵称，其中有大量的重复（总共昵称才不足5000个），要求求出每个昵称的个数。附加信息：昵称不分大小写，按照字典升序输出，昵称长度不超过100（记为L）。

 

解析：将昵称转换小写后，先快排，（O(Lnlongn)）,再扫描一次重复的，（O(Ln)）。

但这样虽然简单却复杂度较高。如果用hash，把字符串当作26进制数，求hash值（O(L)），用线性开放地址法解决hash冲突。这样做，复杂度复杂度为O(Ln)。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const int maxCount=6000;    //hash表的最大槽数

typedef struct {
    char * name;
    int count;
}Student;

//比较大小的接口，用于qsort
int cmp(const void* s1,const void* s2){
    Student *ss1=(Student *)s1;
    Student *ss2=(Student *)s2;
    return strcmp(ss1->name,ss2->name);
}

//生成hash值
int hash(char* str){
    int result=0;
    for(char* p=str;*p!=0;p++){
          result=result*26+(*p)-96;
    }
    return result%maxCount;
}

//转换成小写
char *toLower(char *s){
    char *p;
    for (p=s; *p; p++){
        if (*p >= 'A' && *p <= 'Z')
            *p = *p - 'A' + 'a';
    }
    return s;
}

 Student hashTable[maxCount];
int main(){
   FILE *input=fopen("nickname.in","r");
   FILE *output=fopen("nickname.out","w");
   int n,nickNum;  //nickNum用来记录不重复昵称个数
   int testcase,index;
   char str1[100],str2[100];
  
   for( fscanf(input,"%d",&testcase);testcase>0;testcase--){
        memset(hashTable,0,sizeof(hashTable));
        fscanf(input,"%d",&n); //每一组测试的组数
        for(int i=0;i<n;i++){  //n个昵称
             fscanf(input,"%s",str1);
             strcpy(str2,toLower(str1));
             index=hash(str2);
             //定位应该插入的位置
             while(hashTable[index].name!=NULL&&strcmp(hashTable[index].name,str2)!=0){  //hash冲突
                   index++;
                   if(index>=maxCount)
                        index=0;
              }  
               if(hashTable[index].name==NULL){ //第一次插入
                  hashTable[index].name=new char[strlen(str2)+1];
                  strcpy( hashTable[index].name,str2);
                  hashTable[index].count=1;   
             }else{  //非第一次插入
                  hashTable[index].count++;   
             }
         }
          //将数据前移，然后排序输出
         nickNum=0;
         for(int i=0;i<maxCount;i++){
              if(hashTable[i].count!=0){ 
				  hashTable[nickNum++]=hashTable[i];
				  }
           }       
         qsort(hashTable,nickNum,sizeof(Student),cmp); 
         for(int i=0;i<nickNum;i++){
              fprintf(output,"%s %d\n",hashTable[i].name,hashTable[i].count);
         } 
          fprintf(output,"\n");
    }
    return 0;
}

 输入：

3
3
hello
oh
oh

2
shit
shit

9
hello
put
abs
abs
put
hello
tte
hello
put

 

输出：

hello 1
oh 2

shit 2

abs 2
hello 3
put 3
tte 1